6.2.2 一个人的旅行

一个人的旅行

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 78 Accepted Submission(s): 35

Problem Description

虽然草儿是个路痴（就是在杭电待了一年多，居然还会在校园里迷路的人，汗~),但是草儿仍然很喜欢旅行，因为在旅途中会遇见很多人（白马王子，^0^），很多事，还能丰富自己的阅历，还可以看美丽的风景……草儿想去很多地方，她想要去东京铁塔看夜景，去威尼斯看电影，去阳明山上看海芋，去纽约纯粹看雪景，去巴黎喝咖啡写信，去北京探望孟姜女……眼看寒假就快到了，这么一大段时间，可不能浪费啊，一定要给自己好好的放个假，可是也不能荒废了训练啊，所以草儿决定在要在最短的时间去一个自己想去的地方！因为草儿的家在一个小镇上，没有火车经过，所以她只能去邻近的城市坐火车（好可怜啊~）。

Input

输入数据有多组，每组的第一行是三个整数T，S和D，表示有T条路，和草儿家相邻的城市的有S个，草儿想去的地方有D个；
接着有T行，每行有三个整数a，b，time,表示a,b城市之间的车程是time小时；(1=<(a,b)<=1000;a,b 之间可能有多条路)
接着的第T+1行有S个数，表示和草儿家相连的城市；
接着的第T+2行有D个数，表示草儿想去地方。

Output

输出草儿能去某个喜欢的城市的最短时间。

Sample Input

Sample Output

思路：对于每一个地方算一次最短路，取最小值即可，用的dijkstra，一种堆，Elog(??)

  1 #include <cstdio>
  2 #include <cstring>   
  3 #include <iostream>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <cstdlib>
  7 #include <queue>
  8 using namespace std;
  9 
 10 const int maxn=1110,maxm=20010,INF=10000000;
 11 struct qq
 12 {
 13     int n,to,z,ne;
 14     friend bool operator < (qq a,qq b)
 15     {
 16         return a.z>b.z;
 17     }
 18 } e[maxm],s,ya;
 19 
 20 priority_queue<qq> q;
 21 int d[maxn],node,x,y,z,cnt,to,n,m,h[maxn];
 22 bool f[maxn];
 23 int st[maxn],pp[maxn],ans;
 24 
 25 void addedge(int x,int y,int z)
 26 {
 27     cnt++;
 28     e[cnt].n=x;
 29     e[cnt].to=y;
 30     e[cnt].z=z;
 31     e[cnt].ne=h[x];
 32     h[x]=cnt;
 33 }
 34 
 35 void close()
 36 {
 37     exit(0);
 38 }
 39 
 40 void dijkstra(int st)
 41 {
 42     memset(f,false,sizeof(f));
 43     while (!q.empty())
 44         q.pop();
 45     f[st]=true;
 46     for (int i=1;i<=n;i++)
 47         d[i]=INF;
 48     d[st]=0;
 49     for (int p=h[st];p!=-1;p=e[p].ne)
 50     {
 51         s.n=st;
 52         s.to=e[p].to;
 53         s.z=e[p].z;
 54         q.push(s);
 55     }
 56     while (!q.empty())
 57     {
 58         s=q.top();
 59         q.pop();
 60         to=s.to;
 61         if (f[to]) continue;
 62         d[to]=s.z;
 63         f[to]=true;
 64         for (int p=h[to];p!=-1;p=e[p].ne)
 65         {
 66             node=e[p].to;
 67             if (not f[node])
 68             {
 69                 ya.n=to;
 70                 ya.to=node;
 71                 ya.z=d[to]+e[p].z;
 72                 q.push(ya);
 73             }
 74         }
 75     }
 76 }
 77 
 78 void init()
 79 {
 80 int p,dd;
 81     while (scanf("%d %d %d",&m,&p,&dd)!=EOF)
 82     {
 83         memset(h,-1,sizeof(h));
 84         cnt=0;
 85         for (int i=1;i<=m;i++)
 86         {
 87             scanf("%d %d %d",&x,&y,&z);
 88             addedge(x,y,z);
 89             addedge(y,x,z);
 90             if (x>n)    n=x;
 91             if (y>n)    n=y;
 92         }
 93         for (int i=1;i<=p;i++)
 94             scanf("%d",&st[i]);
 95         for (int i=1;i<=dd;i++)
 96             scanf("%d",&pp[i]);
 97         ans=INF;
 98         for (int i=1;i<=p;i++)
 99         {
100             dijkstra(st[i]);
101             for (int j=1;j<=dd;j++)
102                 if (ans>d[pp[j]])
103                     ans=d[pp[j]];
104         }
105         printf("%d\n",ans);
106     }
107 }
108 
109 
110 int main ()
111 {
112     init();
113     close();
114 }