hd2066一个人的旅行

 1 //如果用队列的话会超时 
 2 #include <stdio.h>
 3 #include <algorithm>
 4 #define INF 0x3f3f3f3f
 5 #define N 1010
 6 using namespace std;
 7 int s, t, d, wp[N], nei[N];
 8 int vis[N], cost[N][N], dis[N];
 9 int min(int x, int y)
10 {
11     return x<y ? x : y;
12 }
13 void dijkstra(int i)
14 {
15     
16     int u, v;
17     for(u = 1; u <= N; u++)
18     {
19         dis[u] = INF;
20         vis[u] = 0;
21     }
22     dis[nei[i]] = 0;
23     while(true)
24     {
25         v = -1;
26         for(u = 1; u <= 1000; u++)
27             if(!vis[u] && (v==-1 || dis[u] < dis[v]))
28                 v = u;
29         if(v == -1)
30             break;
31         vis[v] = 1;
32         for(u = 1; u <= 1000; u++)
33             dis[u] = min(dis[u], dis[v]+cost[v][u]);
34     }
35 }
36 int main()
37 {
38     int i, j;
39     while(~scanf("%d%d%d", &t, &s, &d))
40     {
41         for(i = 1; i < 1000; i++)
42             for(j = i; j <= 1000; j++)
43                 cost[i][j] = cost[j][i] = INF;
44         int a, b, c;
45         while(t--)
46         {
47             scanf("%d%d%d", &a, &b, &c);
48             if(cost[a][b] > c)
49                 cost[a][b] = cost[b][a] = c;
50         }
51         for(i = 1; i <= s; i++)
52             scanf("%d", &nei[i]);
53         for(i = 1; i <= d; i++)
54             scanf("%d", &wp[i]);
55         int min = INF;
56         for(i = 1; i <= s; i++)
57         {
58             dijkstra(i);
59             for(j = 1; j <= d; j++)
60             {
61                 if(min>dis[wp[j]])
62                     min = dis[wp[j]];
63             }
64         }
65         printf("%d\n", min);
66         //printf("%d\n", q.top());
67     }
68     return 0;
69 }