题目大意：一座楼有100层，编号0-99，有n个电梯，每个电梯有不同的速度，并且只在指定的楼层停，在某一层如果有多个电梯停，在两个电梯间转移需要1分钟，求出从0层出发到达k层的所用的最短时间。
本来是正常的单源最短路问题，可是电梯转移花费的时间使得问题复杂了。刚开始是把一个节点扩展成两个节点，一个进一个出，在进出两个节点间加上60s的开销，纠结的好久才憋出来（犯了好多错误...浪费了好长时间），结果却WA了，用别人的测试用例结果也对，忽然就想到可能最终要到0层（写代码时考虑到了，可是认为不会这么干，也就没多写），处理完0之后，就好了...-_-||
1 #include <cstdio> 2 #include <vector> 3 #include <cstring> 4 #include <cctype> 5 using namespace std; 6 #define MAXN 210 7 #define INF 1e8 8 9 int G[MAXN][MAXN], dist[MAXN]; 10 bool vis[MAXN]; 11 12 int main() 13 { 14 #ifdef LOCAL 15 freopen("in", "r", stdin); 16 #endif 17 int n, k; 18 int time[10]; 19 while (scanf("%d%d", &n, &k) != EOF) 20 { 21 for (int i = 0; i < n; i++) 22 scanf("%d", &time[i]); 23 getchar(); 24 for (int i = 0; i < 200; i++) 25 for (int j = 0; j < 200; j++) 26 G[i][j] = INF; 27 for (int i = 0; i < 100; i++) 28 G[i*2][i*2+1] = G[i*2+1][i*2] = 60; 29 for (int i = 0; i < n; i++) 30 { 31 char str[10000]; 32 gets(str); 33 vector<int> v; 34 int len = strlen(str); 35 for (int j = 0; j < len; j++) 36 { 37 if (isdigit(str[j])) 38 { 39 int t = str[j] - '0'; 40 j++; 41 while (j < len && isdigit(str[j])) 42 { 43 t = t * 10 + str[j] - '0'; 44 j++; 45 } 46 v.push_back(t); 47 } 48 } 49 for (int j = 0; j < v.size(); j++) 50 for (int p = j+1; p < v.size(); p++) 51 { 52 int x = v[j], y = v[p]; 53 G[2*x+1][2*y] = G[2*y+1][2*x] = min(G[2*x+1][2*y], (y-x)*time[i]); 54 } 55 } 56 memset(vis, 0, sizeof vis); 57 for (int i = 0; i < 200; i++) 58 dist[i] = INF; 59 dist[1] = 0; 60 if (k) k *= 2; 61 else k = 1; 62 for (int i = 0; i < 200; i++) 63 { 64 int u, lmin = INF; 65 for (int j = 0; j < 200; j++) 66 if (!vis[j] && dist[j] <= lmin) 67 { 68 lmin = dist[j]; 69 u = j; 70 } 71 vis[u] = 1; 72 if (u == k) break; 73 for (int j = 0; j < 200; j++) 74 dist[j] = min(dist[j], dist[u]+G[u][j]); 75 } 76 if (dist[k] != INF) printf("%d ", dist[k]); 77 else printf("IMPOSSIBLE "); 78 } 79 return 0; 80 }
后来看到可以不用这么麻烦，也是，上面那个代码构图时考虑了几次才对了。正常构图，在算权重的时候加上60就可以了（从0扩展出来的不用加60）。
1 #include <cstdio> 2 #include <vector> 3 #include <queue> 4 using namespace std; 5 #define MAXN 110 6 #define INF 1e9 7 #define N 100 8 typedef pair<int, int> ii; 9 typedef vector<ii> vii; 10 11 int G[MAXN][MAXN]; 12 int time[10]; 13 14 int main() 15 { 16 #ifdef LOCAL 17 freopen("in", "r", stdin); 18 #endif 19 int n, k; 20 while (scanf("%d%d", &n, &k) != EOF) 21 { 22 for (int i = 0; i < n; i++) 23 scanf("%d", &time[i]); 24 for (int i = 0; i < N; i++) 25 for (int j = 0; j < N; j++) 26 G[i][j] = INF; 27 for (int i = 0; i < n; i++) 28 { 29 vector<int> v; 30 do 31 { 32 int x; 33 scanf("%d", &x); 34 v.push_back(x); 35 } while (getchar() != ' '); 36 for (int p = 0; p < v.size(); p++) 37 for (int q = p+1; q < v.size(); q++) 38 { 39 int x = v[p], y = v[q]; 40 G[x][y] = G[y][x] = min(G[x][y], (y-x)*time[i]); 41 } 42 } 43 vector<int> dist(N, INF); 44 dist[0] = 0; 45 priority_queue<vii, vector<ii>, greater<ii> > pq; 46 pq.push(ii(0, 0)); 47 while (!pq.empty()) 48 { 49 ii top = pq.top(); 50 pq.pop(); 51 int d = top.first, u = top.second; 52 if (u == k) break; 53 if (d == dist[u]) 54 for (int v = 0; v < N; v++) 55 { 56 if (u == 0) 57 { 58 if (dist[u] + G[u][v] < dist[v]) 59 { 60 dist[v] = dist[u] + G[u][v]; 61 pq.push(ii(dist[v], v)); 62 } 63 } 64 else 65 { 66 if (dist[u] + G[u][v] + 60 < dist[v]) 67 { 68 dist[v] = dist[u] + G[u][v] + 60; 69 pq.push(ii(dist[v], v)); 70 } 71 } 72 } 73 } 74 if (dist[k] != INF) printf("%d ", dist[k]); 75 else printf("IMPOSSIBLE "); 76 } 77 return 0; 78 }