此题中起点有1000个，边有20000条。用链式前向星建图，再枚举起点用SPFA的话，超时了。（按理说，两千万的复杂度应该没超吧。不过一般说计算机计算速度 1~10 千万次/秒。也许拿最烂的计算机来卡时间）
有一个技巧，加一个超级源点。也就是加一个点，使得该点连通所有的起点，并且边的权值为0。这个技巧应用蛮多的。网络流、最小树形图都有题目这样做。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #include<algorithm> 6 using namespace std; 7 const int N = 1010, M=20010; 8 const int INF = 0x3f3f3f3f; 9 struct node 10 { 11 int to, w, next; 12 }; 13 node edge[M]; 14 int head[N], dist[N], outq[N]; 15 bool vis[N]; 16 int tot; 17 bool SPFA(int s, int n ) 18 { 19 int i,k; 20 for(i=0;i<=n;i++) dist[i]=INF; 21 memset(vis,0,sizeof(vis)); 22 memset(outq,0,sizeof(outq)); 23 queue<int > q; 24 while(!q.empty()) q.pop(); 25 vis[s]=1; 26 dist[s]=0; 27 q.push(s); 28 while(!q.empty()) 29 { 30 int u=q.front(); 31 q.pop(); 32 vis[u]=0; 33 outq[u]++; 34 if(outq[u]>n) return 0 ; 35 k=head[u]; 36 while(k>=0) 37 { 38 if(dist[edge[k].to]-edge[k].w>dist[u]) 39 { 40 dist[edge[k].to]=dist[u]+edge[k].w; 41 if(!vis[edge[k].to]) 42 { 43 vis[edge[k].to]=1; 44 q.push(edge[k].to); 45 } 46 } 47 k=edge[k].next; 48 } 49 } 50 return 1; 51 } 52 void addedge(int i,int j,int w) 53 { 54 edge[tot].to=j; 55 edge[tot].w=w; 56 edge[tot].next=head[i]; 57 head[i]=tot++; 58 } 59 void init() 60 { 61 tot=0; 62 memset(head,-1,sizeof(head)); 63 } 64 int main() 65 { 66 //freopen("test.txt","r",stdin); 67 int i,j,k,n,m,t,s; 68 while(scanf("%d%d%d",&n,&m,&t)!=EOF) 69 { 70 init(); 71 while(m--) 72 { 73 scanf("%d%d%d",&i,&j,&k); 74 addedge(i,j,k); 75 } 76 scanf("%d",&k); 77 for(i=0;i<k;i++) 78 { 79 scanf("%d",&s); 80 addedge(n+1,s,0); 81 } 82 SPFA(n+1,n+1); 83 if(dist[t]==INF) printf("-1 "); 84 else printf("%d ",dist[t]); 85 } 86 return 0; 87 }