hdu 2066 一个人的旅行

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define maxn 1001
 6 using namespace std;
 7 
 8 const int inf=1<<28;
 9 
10 int g[maxn][maxn];
11 int a,b,t,max1;
12 int s1[maxn];
13 int d1[maxn];
14 
15 void floyd()
16 {
17     for(int k=1; k<=max1; k++)
18     {
19         for(int i=1; i<=max1; i++)
20         {
21             if(g[i][k]==inf) continue;
22             for(int j=1; j<=max1; j++)
23             {
24                 if(g[i][j]>g[i][k]+g[k][j])
25                 g[i][j]=g[i][k]+g[k][j];
26             }
27         }
28     }
29 }
30 
31 int main()
32 {
33     int T,s,d;
34     while(cin>>T>>s>>d)
35     {
36         for(int i=0; i<=maxn; i++)
37         {
38             for(int j=0; j<=maxn; j++)
39             {
40                 if(i==j) g[i][j]=0;
41                 else g[i][j]=inf;
42             }
43         }
44         max1=-1;
45         for(int i=0; i<T; i++)
46         {
47             scanf("%d%d%d",&a,&b,&t);
48             if(g[a][b]>t) g[a][b]=g[b][a]=t;
49             max1=max(max1,a);
50             max1=max(max1,b);
51         }
52         floyd();
53         for(int i=0; i<s; i++)
54         {
55             scanf("%d",&s1[i]);
56         }
57         for(int j=0; j<d; j++)
58         {
59             scanf("%d",&d1[j]);
60         }
61         int min2=99999999;
62         for(int i=0; i<s; i++)
63         {
64             for(int j=0; j<d; j++)
65             {
66                 min2=min(min2,g[s1[i]][d1[j]]);
67             }
68         }
69         printf("%d\n",min2);
70     }
71     return 0;
72 }