HDU 2066 一个人的旅行

http://acm.hdu.edu.cn/showproblem.php?pid=2066

题意：

输入数据有多组，每组的第一行是三个整数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个数，表示草儿想去地方。

思路：

需要注意一点，a，b可能有多条路，保存最短路。

 1 #include<iostream> 
 2 #include<cstring>
 3 #include<string>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 #define INF 1000001
 8 
 9 int T, S, D, n;
10 
11 int d[1005][1005];
12 int e[1005];
13 int vis[1005], num[1005];
14 
15 
16 void Dijkstra()
17 {
18     int min, pos;
19     vis[0] = 1;
20     for (int i = 0; i <= n; i++)
21         num[i] = d[0][i];
22     for (int i = 1; i <= n; i++)
23     {
24         min = INF;
25         for (int j = 1; j <= n; j++)
26         {
27             if (num[j] < min && !vis[j])
28             {
29                 pos = j;
30                 min = num[j];
31             }
32         }
33         if (min == INF) break;
34         vis[pos] = 1;
35         for (int j = 1; j <= n; j++)
36         {
37             if (num[pos] + d[pos][j] < num[j] && !vis[j])
38                 num[j] = num[pos] + d[pos][j];
39         }
40     }
41 }
42 
43 int main()
44 {
45     //freopen("D:\txt.txt", "r", stdin);
46     int a, b, t;
47     while (~scanf("%d%d%d", &T, &S, &D))
48     {
49         n = 0;
50         memset(vis, 0, sizeof(vis));
51         for (int i = 0; i <= 1005; i++)
52         {
53             d[i][i] = 0;
54             for (int j = i + 1; j <= 1005; j++)
55                 d[i][j] = d[j][i] = INF;
56         }
57 
58         for (int i = 0; i < T; i++)
59         {
60             scanf("%d%d%d", &a, &b, &t);
61             n = max(n, max(a, b));
62             if (t<d[a][b])  d[a][b] = d[b][a] = t;  //这儿需要注意一下，因为两个点之间可能有多条路径，保存最短路
63         }
64 
65         //把家和0点的距离设为0，这样从0出发肯定最先是家
66         for (int i = 0; i < S; i++)
67         {
68             scanf("%d", &a);
69             d[0][a] = d[a][0] = 0;
70         }
71 
72         for (int i = 0; i < D; i++)
73             scanf("%d", &e[i]);
74 
75         Dijkstra();
76 
77         int ans = INF;
78         for (int i = 0; i < D; i++)
79             ans = min(ans, num[e[i]]);
80         printf("%d
", ans);
81     }
82     return 0;
83 }

本来是想用Floyd的，但是不行，超时了。

 1 #include<iostream> 
 2 #include<cstring>
 3 #include<string>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 #define INF 1000001
 8 
 9 int T, S, D;
10 
11 int d[1005][1005];
12 int e[1005];
13 int vis[1005];
14 int p[1005];
15 
16 
17 int main()
18 {
19     //freopen("D:\txt.txt", "r", stdin);
20     int a, b, t;
21     while (~scanf("%d%d%d", &T, &S, &D))
22     {
23         int cnt = 1;
24         for (int i = 0; i <= 1000; i++)
25         {
26             d[i][i] = 0;
27             for (int j = i + 1; j <= 1000; j++)
28                 d[i][j] = d[j][i] = INF;
29         }
30         p[0] = 0;
31         for (int i = 0; i < T; i++)
32         {
33             scanf("%d%d%d", &a, &b, &t);
34             if (!vis[a])
35             {
36                 vis[a] = 1;
37                 p[cnt++] = a;
38             }
39             if (!vis[b])
40             {
41                 vis[b] = 1;
42                 p[cnt++] = b;
43             }
44             if(t < d[a][b])  d[a][b] = d[b][a] = t;
45         }
46 
47         for (int i = 0; i < S; i++)
48         {
49             scanf("%d", &a);
50             d[0][a] = 0;
51             d[a][0] = 0;
52         }
53         for (int i = 0; i < D; i++)
54             scanf("%d", &e[i]);
55 
56         for (int k = 0; k < cnt; k++)
57         for (int i = 0; i < cnt; i++)
58         for (int j = 0; j < cnt; j++)
59             d[p[i]][p[j]] = min(d[p[i]][p[j]], d[p[i]][p[k]] + d[p[k]][p[j]]);
60 
61 
62         int ans = INF;
63         for (int j = 0; j < D; j++)
64             ans = min(ans, d[0][e[j]]);
65         printf("%d
", ans);
66 
67         for (int i = 0; i < cnt; i++)
68             vis[p[i]] = 0;
69     }
70     return 0;
71 }