该最短路可不同于平时简单的最短路模板。

这道题一看就知道用SPFA，但是众所周知，USACO要卡spfa，所以要用更快的算法。

单向边不构成环，双向边都是非负的，所以可以将图分成若干个连通块（内部只有双向边），用拓扑排序的框架处理整张图求解最短路，对于每个入度为0的连通块求一次最短路，因为边权非负，可以用dijkstra。

1 #include
2 using namespace std;
3 const int N=25005,M=150005;
4 int head[N],to[M],nxt[M],edge[M],mark[M],tot;
5 int n,m,p,s,c[N],cnt,deg[N],d[N];
6 bool v[N];
7 queue q;
8 vector a[N];
9 priority_queue > heap;
10
11 void add(int x,int y,int z,int k){
12 nxt[++tot]=head[x];head[x]=tot;to[tot]=y;
13 mark[tot]=k;edge[tot]=z;
14 }
15
16 void dfs(int x){
17 c[x]=cnt;
18 a[cnt].push_back(x);
19 for(int i=head[x];i;i=nxt[i]){
20 if(mark[i]==1) continue;//单向边就跳过
21 int y=to[i];
22 if(!c[y]) dfs(y);
23 }
24 }
25
26 void dijkstra(int k){//算ｋ这一块的最短路
27 for(int j=0;jd[x]+edge[i]){
39 d[y]=d[x]+edge[i];
40 heap.push(make_pair(-d[y],y));
41 }
42 }else{
43 d[y]=min(d[y],d[x]+edge[i]);
44 if(--deg[c[y]]==0) q.push(c[y]);//入度为0加入队列
45 }
46 }
47 }
48 }
49
50 int main(){
51 scanf("%d%d%d%d",&n,&m,&p,&s);
52 for(int i=1;i<=m;i++){ 53 int x,y,z; 54 scanf("%d%d%d",&x,&y,&z); 55 add(x,y,z,0); 56 add(y,x,z,0);//双向边 57 } 58 for(int i=1;i<=p;i++){ 59 int x,y,z; 60 scanf("%d%d%d",&x,&y,&z); 61 add(x,y,z,1); 62 } 63 for(int i=1;i<=n;i++){ 64 if(c[i]==0){ 65 cnt++; 66 dfs(i); 67 } 68 } 69 for(int x=1;x<=n;x++){//统计每个连通块总入度 70 for(int i=head[x];i;i=nxt[i]){ 71 if(mark[i]==0) continue; 72 deg[c[to[i]]]++; 73 } 74 } 75 for(int i=1;i<=cnt;i++)//拓扑排序 76 if(!deg[i]) q.push(i); 77 memset(d,0x3f,sizeof(d)); 78 d[s]=0; 79 while(!q.empty()){ 80 int k=q.front();q.pop();//块号 81 dijkstra(k); 82 } 83 for(int i=1;i<=n;i++){ 84 if(d[i]>n*10000) puts("NO PATH");
85 else printf("%d\n",d[i]);
86 }
87 }