感觉是一道思维和代码难度都很高的题目…

题目分析

大意就是求从起点 $ S $ 到 $ 1 $~$ T $ 每个城镇的最短距离

只是这里路的「边权」和「性质」非常特殊

$\\$

道路 ，$0≤Ci≤10,000$ , 是双向的

航线 , $−10000≤Ci≤10000$ , 且是有向边

$\\$

也就是说既有无向边也有有向边,既有正权边也有负权边

有向无环图本身就不是那么容易处理，而负权边又导致Dijkstra无法正常使用

那么这时候这两种不同的边就不能放在一起处理

可以想到用Dijkstra处理无向图,用拓扑排序处理有向无环图(拓扑序可以解DAG最短路)

当然，用SPFA处理DAG也可以，但可能被卡

且时间复杂度$O(km)$明显大于拓扑排序线性扫描的$O(n)$，因此推荐拓扑排序

$\\$

建图

建图时需要注意把两种不同的边分开来，这样才能用最短路方法求解，否则没有办法求解

这里思路是把航道看成拓扑排序的负权图,自然而然，剩下都是有向无环且是正权的图

于是建图时把航道看成 「边」, 把 道路组成的连通块 看成 「结点」

至此，建图工作算是初步完成

$\\$

代码思路

有了初步思路，如何实现连通块以及Dijkstra与拓扑排序的过程也是有一定设计的

求道路之间连通块:很容易想到DFS,BFS,并查集

因此

• 可以用DFS求解连通块，同时记录附属信息

连通块划分好以后，我们需要在连通块内部跑Dijkstra从而求出一个连通块内的最短路

$\\$

$\\$

$\\$

不过问题是:该从哪个连通块开始呢？

结论是按照拓扑排序顺序用Dijkstra跑连通块,即先处理入度为 $0$ 的连通块

原理是在抽象化的建图以后,本题已经变成两层图的问题了,外层的抽象图便是DAG

从而问题的解决步骤是先对外侧的DAG进行拓扑排序的同时，对对应结点的内层无向图进行处理

此处我认为可以参考复合函数的想法:

例如求解$\large{f(φ(x)) = 10}$,

思路应当是先求解令$f(x) = 10$的 $ x $的取值,再用 $ x $ 的值解出 $ φ(x) $

因此整道题目的大致思路就全部思考完毕了，感觉有一定难度

下见代码

顺带一提,这题用SLF「优化」的SPFA也是可以过的
但是SLF+SPFA最坏时间复杂度可以达到指数级别，不具有普遍性，很容易卡
只需要向起点连一条边权足够大的边就会导致SLF失效

代码

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> pii;

const int N = 25010, M = 150010;//M = 2 * N + N,无向边 + 有向边

vector<int> block[N];
int in[N];//拓扑序的入度
int id[N], bid;//id[i]记录i所在的连通块id,bid计数当前连通块数量
int dist[N];
int h[N], e[M], ne[M], w[M], idx;
int n, m, s, o;
bool st[N];
queue<int> q;

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int bid){
    id[u] = bid;
    block[bid].push_back(u);

    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if(!id[j])
            dfs(j, bid);
    }
}

void dijkstra(int bid){
    priority_queue<pii, vector<pii>, greater<pii> > heap;

    for(auto ver : block[bid]) 
        heap.push({dist[ver], ver});//处理一个连通块(把该连通块所有点dijkstra)

    while(heap.size()){
        auto t = heap.top();
        heap.pop();

        int ver = t.y;
        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver]; ~i; i = ne[i]){
            int j = e[i];
            //核心代码:判断该点是否与ver在同一连通块内
            //如果不在,由于该节点计算完毕，将其入度-1后判断是否入度为0;
            if(id[j] != id[ver] && -- in[id[j]] == 0) q.push(id[j]);  

            if(dist[j] > dist[ver] + w[i]){
                dist[j] = dist[ver] + w[i];
                if(id[j] == id[ver]) heap.push({dist[j], j});
            }

        }    
    }
}

void topsort(){
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;

    for(int i = 1; i <= bid; i ++)
        if(!in[i])
            q.push(i);

    while(q.size()){
        int t = q.front();
        q.pop();

        dijkstra(t);
    }
}

int main(){
    memset(h, -1, sizeof h);
    cin >> o >> n >> m >> s;
    while(n --){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }

    //dfs处理连通块
    for(int i = 1; i <= o; i ++)
        if(!id[i])
            dfs(i, ++ bid);

    while(m --){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        in[id[b]] ++ ;
    }

    topsort();

    for(int i = 1; i <= o; i ++)
        if(dist[i] > 0x3f3f3f3f / 2)puts("NO PATH");//由于有负权边,所以只要结果>题目可能值就说明不可能
        else printf("%d\n", dist[i]);

    return 0;
}