NYoj 155最短路

 1 //dij
 2 #include<stdio.h>
 3 
 4 #include<string.h>
 5 #include<queue>
 6 using namespace std;
 7 #define inf 0x3f3f3f3f
 8 #define min(x,y) (x<y?x:y)
 9 
10 int N,M,P,Q;
11 int city[105],dist[1005],cost[1005][1005];
12 bool vis[1005];
13 
14 void dij(){
15     for(int i=1;i<=M;i++){
16         dist[i]=inf;
17     }
18     dist[Q]=0;
19     memset(vis,false,sizeof(vis));
20     for(int i=1;i<=M;i++){
21         int mmin=inf,pre=-1;
22         for(int j=1;j<=M;j++){
23             if(!vis[j]&&dist[j]<mmin){
24                 mmin=dist[j];
25                 pre=j;
26             }
27             }
28         vis[pre]=true;
29         for(int j=1;j<=M;j++){
30             if(cost[pre][j]==0){
31                 continue;
32             }
33             if(!vis[j]&&cost[pre][j]+dist[pre]<dist[j]){
34                 dist[j]=cost[pre][j]+dist[pre];
35             }
36         }
37     }
38 }
39 
40 int main(){
41     int T;
42     scanf("%d",&T);
43     while(T--){
44         scanf("%d%d%d%d",&N,&M,&P,&Q);
45         for(int i=0;i<N;i++){
46             scanf("%d",&city[i]);
47         }
48         memset(cost,0,sizeof(cost));
49         for(int i=0;i<P;i++){
50             int a,b,c;
51             scanf("%d%d%d",&a,&b,&c);
52             if(cost[a][b]==0){
53                 cost[a][b]=cost[b][a]=c;
54                 continue;
55             }
56             cost[a][b]=cost[b][a]=min(cost[a][b],c);
57         }
58         dij();
59         int ans=dist[city[0]];
60         for(int i=1;i<N;i++){
61             ans=min(ans,dist[city[i]]);
62         }
63         printf("%d
",ans);
64     }
65 }