题意：n个点，有m1条双向边，m2条单向边，双向边边长非负，单向边可能为负
保证如果有一条从x到y的单项边，则不可能存在从y到x的路径
问从S出发到其他所有点的最短路
n<=25000，n1,m2<=5e4，边权绝对值<=1e4
思路：听说银川出10年前USACO的原题？
负权边不能直接dijkstra，SPFA又会TLE
考虑这题的特殊限制：双向边边长非负，单向边可能为负，保证如果有一条从x到y的单向边，则不可能存在从y到x的路径
由此可知如果把所有联通性相同的点缩成一个分量，则负权的单向边只可能在不同的分量之间出现，且无负环
用并查集维护分量，将分量拓扑排序，按分量的拓扑序依次将边和点加入，跑dijkstra
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned int uint; 5 typedef unsigned long long ull; 6 typedef pair<int,int> PII; 7 typedef pair<ll,ll> Pll; 8 typedef vector<int> VI; 9 typedef vector<PII> VII; 10 //typedef pair<ll,ll>P; 11 #define N 300010 12 #define M 200010 13 #define fi first 14 #define se second 15 #define MP make_pair 16 #define pb push_back 17 #define pi acos(-1) 18 #define mem(a,b) memset(a,b,sizeof(a)) 19 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++) 20 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--) 21 #define lowbit(x) x&(-x) 22 #define Rand (rand()*(1<<16)+rand()) 23 #define id(x) ((x)<=B?(x):m-n/(x)+1) 24 #define ls p<<1 25 #define rs p<<1|1 26 27 const //ll MOD=1e9+7,inv2=(MOD+1)/2; 28 double eps=1e-6; 29 int INF=1e9; 30 int dx[4]={-1,1,0,0}; 31 int dy[4]={0,0,-1,1}; 32 33 struct edge 34 { 35 int x,y,z; 36 edge()=default; 37 edge(int x,int y,int z):x(x),y(y),z(z){} 38 }a[N],b[N]; 39 40 vector<edge>c[N]; 41 vector<int>p[N]; 42 int head[N],vet[N],nxt[N],len[N],flag[N],s[N],num[N],dis[N],vis[N],f[N],d[N],q[N], 43 tot,id,n,m1,m2,S; 44 45 int read() 46 { 47 int v=0,f=1; 48 char c=getchar(); 49 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 50 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 51 return v*f; 52 } 53 54 void add(int a,int b,int c) 55 { 56 nxt[++tot]=head[a]; 57 vet[tot]=b; 58 len[tot]=c; 59 head[a]=tot; 60 } 61 62 int find(int k) 63 { 64 if(f[k]!=k) f[k]=find(f[k]); 65 return f[k]; 66 } 67 68 void topo() 69 { 70 rep(i,1,n) f[i]=i; 71 rep(i,1,m1) 72 { 73 int p=find(a[i].x),q=find(a[i].y); 74 if(p!=q) f[p]=q; 75 } 76 rep(i,1,n) head[i]=d[i]=0; 77 tot=0; 78 rep(i,1,m2) 79 { 80 int p=find(b[i].x),q=find(b[i].y); 81 if(p!=q) 82 { 83 d[q]++; add(p,q,0); 84 } 85 } 86 int t=0,w=0; 87 id=0; 88 rep(i,1,n) 89 if(f[i]==i&&d[i]==0){w++; q[w]=i;} 90 while(t<w) 91 { 92 t++; 93 int u=q[t]; 94 s[u]=++id; 95 int e=head[u]; 96 while(e) 97 { 98 int v=vet[e]; 99 d[v]--; 100 if(d[v]==0){w++; q[w]=v;} 101 e=nxt[e]; 102 } 103 } 104 rep(i,1,n) 105 { 106 num[i]=s[find(i)]; 107 p[num[i]].pb(i); 108 } 109 110 rep(i,1,m1) 111 { 112 int x=num[a[i].x]; 113 c[x].pb(edge(a[i].x,a[i].y,a[i].z)); 114 c[x].pb(edge(a[i].y,a[i].x,a[i].z)); 115 } 116 rep(i,1,m2) 117 { 118 int x=num[b[i].x]; 119 c[x].pb(edge(b[i].x,b[i].y,b[i].z)); 120 } 121 122 } 123 124 void solve() 125 { 126 priority_queue<PII> q; 127 rep(i,1,n) head[i]=vis[i]=0; 128 tot=0; 129 rep(i,1,n) dis[i]=INF; 130 dis[S]=0; 131 rep(i,1,id) 132 { 133 for(int j=0;j<p[i].size();j++) 134 { 135 int x=p[i][j]; 136 q.push(MP(-dis[x],x)); 137 } 138 for(int j=0;j<c[i].size();j++) 139 { 140 int x=c[i][j].x,y=c[i][j].y,z=c[i][j].z; 141 add(x,y,z); 142 } 143 144 while(!q.empty()) 145 { 146 int u=q.top().se; 147 q.pop(); 148 if(vis[u]) continue; 149 vis[u]=1; 150 int e=head[u]; 151 while(e) 152 { 153 int v=vet[e]; 154 if(dis[u]+len[e]<dis[v]) 155 { 156 dis[v]=dis[u]+len[e]; 157 if(num[v]<=i) q.push(MP(-dis[v],v)); 158 } 159 e=nxt[e]; 160 } 161 } 162 } 163 rep(i,1,n) 164 if(dis[i]>5e8) printf("NO PATH\n"); 165 else printf("%d\n",dis[i]); 166 } 167 168 int main() 169 { 170 n=read(),m1=read(),m2=read(),S=read(); 171 rep(i,1,m1) a[i].x=read(),a[i].y=read(),a[i].z=read(); 172 rep(i,1,m2) b[i].x=read(),b[i].y=read(),b[i].z=read(); 173 topo(); 174 solve(); 175 return 0; 176 }