NYOJ-115 Dijlstra

原题链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=115
 1 #include"iostream"
 2 #include"stdio.h"
 3 #include"algorithm"
 4 #include"string.h"
 5 using namespace std;
 6 #define INF 99999999 
 7 #define MAXN 1005
 8 int map[MAXN][MAXN];//邻接矩阵
 9 int dis[MAXN]; //记录单元最段路径
10 int visited[MAXN]; //F为访问0，已访问1
11 int nux[MAXN]; //第I个军队驻扎在 nux【i】个城市 
12 int N;
13 int M;
14 int P;
15 int Q;
16 void dijkstra(int s){//s到个点距离 
17         memset(visited,0,sizeof(visited));
18         visited[s]=1;
19         for(int i=1;i<=M;i++)
20                 dis[i]=map[s][i];    
21         for(int i=1;i<=M;i++){
22             int minn=INF;
23             int u;
24             for(int j=1;j<=M;j++){
25                 if(visited[j]==0&&dis[j]<minn){
26                     minn=dis[j];
27                     u=j;
28                 }
29             }
30             visited[u]=1;
31              for(int v=1;v<=M;v++){
32                  if(visited[v]==0&&map[u][v]<INF&&dis[v]>dis[u]+map[u][v])
33                      dis[v]=dis[u]+map[u][v];
34              }
35         }
36 }
37 int main()
38 {
39     int T;
40     scanf("%d",&T);
41     while(T--)
42     {
43         scanf("%d%d%d%d",&N,&M,&P,&Q);
44         for(int i=0; i<=M; i++)//初始化邻接矩阵
45             for(int j=0; j<=M; j++)
46                 i==j?map[i][j]=0:map[i][j]=INF;
47         for(int i=1; i<=N; i++) //部队驻扎的城市
48             scanf("%d",&nux[i]);
49         int a,b,t;//临时接收数据
50         while(P--)
51         {
52             scanf("%d%d%d",&a,&b,&t);
53             if(map[a][b]>t)
54                 map[a][b]=map[b][a]=t;//无向图
55         }
56         int min_time=INF;//最短时间
57         dijkstra(Q);
58         for(int i=1; i<=N; i++)//寻找最短时间
59             min_time=min(min_time,dis[nux[i]]);
60         printf("%d
",min_time);
61     }
62     return 0;
63 }