第一遍用dijkstra写完 发现超时
然后
反过来写的话只要一次dijkstra
要点：此题为有向图 反着dijkstra的话要反着存路径
#include<bits/stdc++.h> using namespace std; int m1[1005][1005]; int vis[1005];int dis[1005]; #define INF 99999 int n,e,cas; void dijkstra(int v0) { memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)dis[i]=m1[v0][i]; // for(int i=1;i<=n;i++)printf("%d ",dis[i]);cout<<endl; vis[v0]=1; for(int i=0;i<n-1;i++) { int minn=INF,u=v0; for(int j=1;j<=n;j++) { if(vis[j]==0&&dis[j]<minn) { u=j;minn=dis[j]; } } vis[u]=1; for(int j=1;j<=n;j++) { if(vis[j]==0&&dis[u]+m1[u][j]<dis[j]) { dis[j]=dis[u]+m1[u][j]; } } } } int main() { while(scanf("%d%d%d",&n,&cas,&e)==3) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(i==j)m1[i][j]=0; else m1[i][j]=INF; } while(cas--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(m1[b][a]>c)m1[b][a]=c; } // for(int i=1;i<=n;i++){ // for(int j=1;j<=n;j++) // printf("%5d ",m1[i][j]); // printf(" ");} int q;scanf("%d",&q); int min1=INF; dijkstra(e); // for(int i=1;i<=n;i++)printf("%d ",dis[i]);cout<<endl; for(int i=1;i<=q;i++) { int x; scanf("%d",&x); if(dis[x]<min1){min1=dis[x];} } if(min1!=INF) printf("%d ",min1); else printf("-1 "); } }