UVa 10801 电梯换乘

题意：
有多个电梯，每个电梯只能到达指定楼层，每个电梯有速度，如果中途换乘电梯，需要额外加60s，求从0层到达k层的最少时间。

思路：
想了一下知道这是个最短路的问题。

首先我们用邻接矩阵来存储楼层i和j之间的最少时间，此时存储的i到j肯定是一个电梯搭乘上去的，接下来Dijkstra寻找最短路，注意一下寻找最短路时的状态更新。举个例子来说，比如我们第一次找到的最少时间是0~3层，此时更新第3层到别的层数的时间，如果此时不换乘电梯，那么d[3]+G[3][k]=d[k]，此时不需要更新。如果换乘电梯，那么需要额外的+60s，此时判断d[3]+G[3][k]+60是否小于d[k]。所以用这样的一个式子就可以来判断是否需要更新状态。

 1 #include<iostream> 
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<string>
 5 using namespace std;
 6 
 7 const int INF = 0x3f3f3f3f;
 8 
 9 int n, k;
10 int t[6];
11 int G[105][105];
12 int vis[105];
13 int num[105];
14 int m[105];
15 
16 void graph(int k, int count)
17 {
18     for (int i = 0; i < count; i++)
19     for (int j = i + 1; j < count; j++)
20     {
21         int u = m[i], v = m[j], w = (v - u)*t[k];
22         if (w<G[u][v])
23             G[u][v] = G[v][u] = w;
24     }
25     return;
26 }
27 
28 void Dijkstra()
29 {
30     memset(vis, 0, sizeof(vis));
31     for (int i = 1; i <= 99; i++)
32         num[i] = G[0][i];
33     vis[0] = 1;
34     num[0] = 0;
35     for (int i = 0; i < 99; i++)
36     {
37         int flag = 0;
38         int min = INF;
39         int u;
40         for (int k = 0; k <= 99; k++)
41         {
42             if (!vis[k] && num[k] < min)
43             {
44                 u = k;
45                 min = num[k];
46                 flag = 1;
47             }
48         }
49         if (!flag)  break;
50         vis[u] = 1;
51         for (int j = 0; j <= 99; j++)
52         {
53             if (!vis[j] && num[u] + G[u][j] + 60 < num[j])
54                 num[j] = num[u] + G[u][j] + 60;
55         }
56     }
57 }
58 
59 int main()
60 {
61     //freopen("D:\txt.txt", "r", stdin);
62     while (cin >> n >> k)
63     {
64         memset(G, INF, sizeof(G));
65         for (int i = 0; i < n; i++)
66             cin >> t[i];
67         for (int i = 0; i < n; i++)
68         {
69             int count = 0;
70             while (1)
71             {
72                 scanf("%d", &m[count++]);
73                 char ch = getchar();
74                 if (ch !=' ')
75                     break;
76             }
77             graph(i, count); 
78         }
79         Dijkstra();
80         if (num[k] == INF)
81             cout << "IMPOSSIBLE" << endl;
82         else if (k == 0)
83             cout << "0" << endl;
84         else
85             cout << num[k]  << endl;
86     }
87 }