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
| #include <bits/stdc++.h> #define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; const int MAXN=500000; const int INF=0x3f3f3f3f; struct node{ int to,next,w; }e[MAXN]; struct Node{ int u,d; bool operator<(const Node &o)const{ return d>o.d; } }; int head[MAXN],dis[MAXN],id[MAXN],in[MAXN]; int n,r,p,s,tot,bcnt; bool vis[MAXN]; vector<int> ve[MAXN]; queue<int> q; priority_queue<Node> pq; void add(int u,int v,int w){ e[tot]={v,head[u],w}; head[u]=tot++; } void dfs(int x){ ve[bcnt].push_back(x); id[x]=bcnt; for(int i=head[x];~i;i=e[i].next){ if(!id[e[i].to]) dfs(e[i].to); } } void dij(int s){ for(auto i:ve[s]) pq.push({i,dis[i]}); while(!pq.empty()){ Node now=pq.top(); pq.pop(); if(vis[now.u]) continue; vis[now.u]=1; for(int i=head[now.u];~i;i=e[i].next){ int v=e[i].to,w=e[i].w; if(dis[v]>dis[now.u]+w){ dis[v]=dis[now.u]+w; if(id[v]==id[now.u]) pq.push({v,dis[v]}); } if(id[v]!=id[now.u]){ in[id[v]]--; if(in[id[v]]==0) q.push(id[v]); } } } } void tupo(){ memset(dis,0x3f,sizeof dis); dis[s]=0; q.push(id[s]); for(int i=1;i<=bcnt;i++){ if(!in[i]) q.push(i); } while(!q.empty()){ int fr=q.front(); q.pop(); dij(fr); } } int main() { ios; memset(head,-1,sizeof head); cin>>n>>r>>p>>s; while(r--){ int u,v,w; cin>>u>>v>>w; add(u,v,w); add(v,u,w); } for(int i=1;i<=n;i++){ if(!id[i]){ bcnt++; dfs(i); } } while(p--){ int u,v,w; cin>>u>>v>>w; add(u,v,w); in[id[v]]++; } tupo(); for(int i=1;i<=n;i++){ if(dis[i]>INF/2) cout<<"NO PATH"<<'\n'; else cout<<dis[i]<<'\n'; } return 0; }
|