http://acm.hdu.edu.cn/showproblem.php?pid=2680
这道题是有向图。把全部可以出发的点进队列spfa就可以。
1 #include <cstdio> 2 #include <vector> 3 #include <queue> 4 #include <cstring> 5 #include <algorithm> 6 #define maxn 1001 7 using namespace std; 8 const int inf=1<<28; 9 10 int n,m,s; 11 int p,q,t; 12 int g[maxn][maxn]; 13 int dis[maxn]; 14 int c[maxn]; 15 int w; 16 bool vis[maxn]; 17 void dijstra(int src) 18 { 19 memset(vis,false,sizeof(vis)); 20 for(int i=1; i<=n; i++) dis[i]=inf; 21 dis[src]=0; 22 for(int i=1; i<=n; i++) 23 { 24 int x,m=inf; 25 for(int y=1; y<=n; y++) if(!vis[y]&&dis[y]<m) m=dis[x=y]; 26 vis[x]=true; 27 for(int y=1; y<=n; y++) dis[y]=min(dis[y],dis[x]+g[x][y]); 28 } 29 } 30 31 void spfa() 32 { 33 queue<int>q; 34 memset(vis,false,sizeof(vis)); 35 for(int i=1; i<=n; i++) dis[i]=inf; 36 for(int i=0; i<w; i++) 37 { 38 dis[c[i]]=0; 39 vis[c[i]]=true; 40 q.push(c[i]); 41 } 42 while(!q.empty()) 43 { 44 int u=q.front(); 45 q.pop(); 46 vis[u]=false; 47 for(int i=1; i<=n; i++) 48 { 49 if(dis[i]>dis[u]+g[u][i]&&g[u][i]!=inf) 50 { 51 dis[i]=dis[u]+g[u][i]; 52 if(!vis[i]) 53 { 54 vis[i]=true; 55 q.push(i); 56 } 57 } 58 } 59 } 60 } 61 62 int main() 63 { 64 while(scanf("%d%d%d",&n,&m,&s)!=EOF) 65 { 66 for(int i=1; i<=n; i++) 67 { 68 for(int j=1; j<=n; j++) 69 { 70 g[i][j]=inf; 71 } 72 } 73 for(int i=0; i<m; i++) 74 { 75 scanf("%d%d%d",&p,&q,&t); 76 g[p][q]=min(g[p][q],t); 77 } 78 scanf("%d",&w); 79 for(int i=0; i<w; i++) 80 { 81 scanf("%d",&c[i]); 82 } 83 spfa(); 84 if(dis[s]==inf) 85 printf("-1 "); 86 else printf("%d ",dis[s]); 87 } 88 return 0; 89 }