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 101 102 103 104 105 106 107 108
|
#include <cstdio> #include <algorithm> #include <queue> #include <cmath> #include <vector> #include <cstring> using namespace std;
typedef long long ll; #define inf 0x3f3f3f3f const int N = 3e5 + 10; const int mod = 1e9 + 7; struct { int to, w; } e; vector<edge> g[N]; void addedge(int u, int v, int w) { e.to = v; e.w = w; g[u].push_back(e); } int n, r, p, s, f[N], vis[N], cnt, dis[N], dig[N]; queue<int> tuo; priority_queue<pair<int, int>> q; void dfs(int x) { f[x] = cnt; vis[x] = 1; for (int i = 0; i < g[x].size(); i++) if (!vis[g[x][i].to]) dfs(g[x][i].to); }
int main() { scanf("%d%d%d%d", &n, &r, &p, &s); for (int i = 1; i <= r; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); addedge(v, u, w); } for (int i = 1; i <= n; i++) if (!vis[i]) ++cnt, dfs(i); for (int i = 1; i <= p; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); dig[f[v]]++; } memset(vis, 0, sizeof(vis)); memset(dis, 0x7f, sizeof(dis)); tuo.push(f[s]); for (int i = 1; i <= cnt; i++) if (!dig[i]) tuo.push(i); dis[s] = 0; while (!tuo.empty()) { int u = tuo.front(); tuo.pop(); for (int i = 1; i <= n; i++) if (f[i] == u) q.push(make_pair(-dis[i], i)); while (!q.empty()) { int x = q.top().second; q.pop(); if (vis[x]) continue; vis[x] = 1; for (int i = 0; i < g[x].size(); i++) {
int v = g[x][i].to; int w = g[x][i].w; if (dis[v] > w + dis[x]) { dis[v] = w + dis[x]; if (f[v] == f[x]) q.push(make_pair(-dis[v], v)); } if (f[v] != f[x]) { dig[f[v]]--; if (dig[f[v]] == 0) tuo.push(f[v]); } } } } for (int i = 1; i <= n; i++) if (dis[i] >= inf) printf("NO PATHn"); else printf("%dn", dis[i]); }
|
近期评论