NYOJ-115 Dijlstra

原题链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=115

 #include"iostream"

 #include"stdio.h"

 #include"algorithm"

 #include"string.h"

 using namespace std;

 #define INF 99999999

 #define MAXN 1005

 int map[MAXN][MAXN];//邻接矩阵

 int dis[MAXN]; //记录单元最段路径

 int visited[MAXN]; //F为访问0，已访问1

 int nux[MAXN]; //第I个军队驻扎在 nux【i】个城市

 int N;

 int M;

 int P;

 int Q;

 void dijkstra(int s){//s到个点距离

         memset(visited,,sizeof(visited));

         visited[s]=;

         for(int i=;i<=M;i++)

                 dis[i]=map[s][i];

         for(int i=;i<=M;i++){

             int minn=INF;

             int u;

             for(int j=;j<=M;j++){

                 if(visited[j]==&&dis[j]<minn){

                     minn=dis[j];

                     u=j;

                 }

             }

             visited[u]=;

              for(int v=;v<=M;v++){

                  if(visited[v]==&&map[u][v]<INF&&dis[v]>dis[u]+map[u][v])

                      dis[v]=dis[u]+map[u][v];

              }

         }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d%d%d",&N,&M,&P,&Q);

         for(int i=; i<=M; i++)//初始化邻接矩阵

             for(int j=; j<=M; j++)

                 i==j?map[i][j]=:map[i][j]=INF;

         for(int i=; i<=N; i++) //部队驻扎的城市

             scanf("%d",&nux[i]);

         int a,b,t;//临时接收数据

         while(P--)

         {

             scanf("%d%d%d",&a,&b,&t);

             if(map[a][b]>t)

                 map[a][b]=map[b][a]=t;//无向图

         }

         int min_time=INF;//最短时间

         dijkstra(Q);

         for(int i=; i<=N; i++)//寻找最短时间

             min_time=min(min_time,dis[nux[i]]);

         printf("%d\n",min_time);

     }

     return ;

 }