Luogu 3008 [USACO11JAN]道路和飞机Roads and Planes

BZOJ2200

听说加上slf优化的spfa的卡过，真的不想写这些东西。

考虑使用堆优化的dij算法。

先加上所有双向边，然后dfs一下搜出所有由双向边构成的联通块，然后加上所有的单向边，一边对所有联通块拓扑排序一边在联通块内部处理最短路，因为所有的双向边都是不带负权的，而单向边都是有负权的，所以这样规避dij贪心的错误之处。

注意到一个$inf$可能被另一个$inf$加上一个负权边拓展得到，所以最后的答案可能会小于$inf$，检验的时候注意取的极大值要小于一开始赋的$inf$。

时间复杂度$O(nlogn)$。

Code：

#include <cstdio>

#include <cstring>

#include <queue>

#include <iostream>

#include <vector>

using namespace std;

typedef pair <int, int> pin;

const int N = ;

const int M = 2e5 + ;

const int inf = 1e8;

int n, m1, m2, st, tot = , head[N], dis[N];

int l = , r = , q[N], deg[N], sccCnt = , bel[N];

bool vis[N];

vector <int> scc[N];

struct Edge {

    int to, nxt, val;

} e[M];

inline void add(int from, int to, int val) {

    e[++tot].to = to;

    e[tot].val = val;

    e[tot].nxt = head[from];

    head[from] = tot;

}

template <typename T>

inline void read(T &X) {

    X = ; char ch = ; T op = ;

    for(; ch > ''|| ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

void dfs(int x) {

    bel[x] = sccCnt, scc[sccCnt].push_back(x);

    for(int i = head[x]; i; i = e[i].nxt) {

        int y = e[i].to;

        if(!bel[y]) dfs(y);

    }

}

priority_queue <pin> Q;

void dij(int c) {

    for(unsigned int i = ; i < scc[c].size(); i++) Q.push(pin(-dis[scc[c][i]], scc[c][i]));

    for(; !Q.empty(); ) {

        int x = Q.top().second; Q.pop();

        if(vis[x]) continue;

        vis[x] = ;

        for(int i = head[x]; i; i = e[i].nxt) {

            int y = e[i].to;

            if(bel[y] == c) {

                if(dis[y] > dis[x] + e[i].val) {

                    dis[y] = dis[x] + e[i].val;

                    Q.push(pin(-dis[y], y));

                }

            } else {

                if(dis[y] > dis[x] + e[i].val) dis[y] = dis[x] + e[i].val;

                deg[bel[y]]--;

                if(!deg[bel[y]]) q[++r] = bel[y];

            }

        }

    }

}

int main() {

    read(n), read(m1), read(m2), read(st);

    for(int x, y, v, i = ; i <= m1; i++) {

        read(x), read(y), read(v);

        add(x, y, v), add(y, x, v);

    }

    for(int i = ; i <= n; i++)

        if(!bel[i]) ++sccCnt, dfs(i);

    for(int x, y, v, i = ; i <= m2; i++) {

        read(x), read(y), read(v);

        add(x, y, v);

        deg[bel[y]]++;

    }

    for(int i = ; i <= sccCnt; i++)

        if(!deg[i]) q[++r] = i;

    memset(dis, 0x3f, sizeof(dis)); dis[st] = ;

    for(; l <= r; ++l) dij(q[l]);

    for(int i = ; i <= n; i++) {

        if(dis[i] > inf) puts("NO PATH");

        else printf("%d\n", dis[i]);

    }

    return ;

}