「SDOI 2010」大陆争霸

题目大意：给定一张图，访问一些点前要先访问其他的点，流量为 $\inf$，求从 $1\rightarrow n$ 的最短路。$n \leq 3000$

带限制的最短路，注意要在 $dijkstra$ 内部进行拓扑，当一个点的入度为 $0$ 时才能加入优先队列。

$dis1$ 表示可以到达的最早时刻，$dis2$ 表示可以访问的最早时刻，则 $\max(dis1,dis2)$ 就是实际经过的最早时刻。

#include <cstdio>
#include <cstring>
#include <queue>

const int N = 3005, M = 70005;
struct Edge {
    int v, w;
} e[M];
struct Pair {
    int x, y;
    bool operator < (const Pair rhs) const {
        return x > rhs.x;
    }
};
std::priority_queue<Pair> Q;
int head1[N], nxt1[M], head2[N], nxt2[M], v[M], dis1[N], dis2[N], vis[N], dgr[N], tot1, tot2, n, m;

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
int max(int x, int y) {
    return x > y ? x : y;
}
void add_edge1(int u, int v, int w) {
    nxt1[++tot1] = head1[u];
    head1[u] = tot1, e[tot1] = (Edge){v, w};
}
void add_edge2(int from, int to) {
    nxt2[++tot2] = head2[from];
    head2[from] = tot2, v[tot2] = to;
}
void dijkstra() {
    memset(dis1, 0x3f, sizeof dis1);
    dis1[1] = 0, Q.push((Pair){0, 1});
    int cnt = 0;
    while (!Q.empty()) {
        int u = Q.top().y; Q.pop();
        if (vis[u]) continue;
        if (++cnt == n) break;
        vis[u] = 1;
        int mx = max(dis1[u], dis2[u]);
        for (int i = head1[u]; i; i = nxt1[i])
            if (dis1[e[i].v] > mx + e[i].w) {
                dis1[e[i].v] = mx + e[i].w;
                if (!dgr[e[i].v]) Q.push((Pair){max(dis1[e[i].v], dis2[e[i].v]), e[i].v});
            }
        for (int i = head2[u]; i; i = nxt2[i]) {
            dis2[v[i]] = max(dis2[v[i]], mx);
            if (--dgr[v[i]] == 0) Q.push((Pair){max(dis1[v[i]], dis2[v[i]]), v[i]});
        }
    }
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read(), w = read();
        if (u != v) add_edge1(u, v, w);
    }
    for (int i = 1; i <= n; ++i) {
        dgr[i] = read();
        for (int j = 1; j <= dgr[i]; ++j)
            add_edge2(read(), i);
    }
    dijkstra();
    printf("%d\n", max(dis1[n], dis2[n]));
    return 0;
}