342. 道路与航线

思路

根据道路可以把图看成很多个团，那么航线就是连接团的有向边，从S到某个T的最短路径，可以看成S经过若干个团(且必须经过)后达到T所在的团的起点 $T_s$ 的最短路+ $dis_{T_s\rightarrow T}$

需要预处理出所有的团，可以根据点获得团，也可以根据团找到所有的点

然后对团做拓扑排序，依次处理每个团，在处理团内的点$v_x$时，对于它的某一个邻点$v_y$，如果$v_x$和$v_y$不是同一个团，则$v_y$所在的团就可以入队了，否则，可以更新$dist_{v_y}$(如果可以的话)。

由于每个团内部都是道路结点，因此可以团内使用dijkstra算法。

如果不采用以上算法的话，也可以使用spfa,不过需要有一些优化算法，这里不作赘述。

AC code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
using pii = pair<int,int>;

const int N = 25010, M = 150010, inf = 0x3f3f3f3f;
int h[N], e[M], ne[M], w[M], idx;
int id[N], din[N], dist[N];
bool st[N];
vector<int> block[N];
queue<int> q;
int n, mr, mp, s, bcnt;

void add(int a, int b, int c);
void dfs(int u, int bidx);
void topsort();
void dijkstra(int t);

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 bidx){
    id[u] = bidx;
    block[bidx].push_back(u);
    for(int i = h[u]; ~i; i = ne[i]){
        int j = e[i];
        if(!id[j]) dfs(j, bidx);
    }
}

void topsort(){
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    for(int i = 1; i <= bcnt; i++){
        if(din[i] == 0) q.push(i);
    }
    while(q.size()){
        int t = q.front(); 
        q.pop();
        dijkstra(t);
    }
}

void dijkstra(int t){
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    for(auto p : block[t]){
        pq.push({dist[p], p});
    }
    while(pq.size()){
        auto p = pq.top(); pq.pop();
        int x = p.first, y = p.second;
        if(st[y]) continue;
        st[y] = true;
        for(int i = h[y]; ~i; i = ne[i]){
            int j = e[i];
            if(dist[j] > x + w[i]){
                dist[j] = x + w[i];
                if(id[j] == id[y]) pq.push({dist[j], j});
            }
            if(id[j] != id[y] && --din[id[j]] == 0) q.push(id[j]);
        }
    }
}

int main(){
    cin >> n >> mr >> mp >> s;
    
    memset(h, 0xff, sizeof(h));
    // 输入道路节点
    for(int i = 0; i < mr; i++){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    // 确定团
    for(int i = 1; i <= n; i++){
        if(!id[i]) dfs(i, ++bcnt);
    }
    // 输入航线
    for(int i = 0; i < mp; i++){
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        din[id[b]]++;
    }
    // 对团做拓扑排序 & dist计算
    topsort();

    for(int i = 1; i <= n; i++){
        if(dist[i] > inf / 2) puts("NO PATH");
        else cout << dist[i] << endl;
    }
    return 0;
}