题目

代码

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 25e3+10, M = 15e4+10;
const int inf = 0x3f3f3f3f; 
int h[N], e[M], ne[M], idx, w[M];
int id[N], bcnt;
vector<int> block[N];
int in[N];
int dist[N];
bool st[N];
int n, r, p, s;
queue<int> q;
void add(int a, int b, int c)  // 添加一条边a->b，边权为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>> hp;for(auto c : block[bid])hp.push({dist[c], c}); //全部压入的原因是要找出块内（Dijkstra的范围）dist最小的点while(hp.size()){int u = hp.top().y; hp.pop();if(st[u]) continue;st[u] = true;for(int i = h[u]; ~i; i = ne[i]){int j = e[i];if(dist[j] > dist[u] + w[i]){dist[j] = dist[u] + w[i];if(id[u] == id[j]){hp.push({dist[j], j});}}if(id[u] != id[j] && --in[id[j]] == 0) q.push(id[j]); //注意这一步要在上面的 if 外头}}
}
void topsort()
{memset(st, 0, sizeof st);memset(dist, 0x3f, sizeof dist);dist[s] = 0;for(int i = 1; i <= bcnt; i++){if(in[i] == 0) q.push(i);}while(q.size()){int u = q.front(); q.pop();dijkstra(u);}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cin >> n >> r >> p >> s;memset(h, -1, sizeof h);for(int i = 1; i <= r; 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 = 1; i <= p; i++){int a, b, c;cin >> a >> b >> c;add(a, b, c);in[id[b]]++;}topsort();for(int i = 1; i <= n; i++){if(dist[i] > inf / 2) cout << "NO PATH\n";else cout << dist[i] << '\n';}
}