UVa 10841 - Lift Hopping in the Real World

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

在一棟高樓中有 N 台電梯,每個電梯停靠的樓層有所限制,同時每一台電梯在相鄰樓層移動的所需時間也不同。轉換電梯 (出電梯) 需要 5 秒的時間,然後可以轉搭其他電梯。並不曉得一開始電梯停靠在那一個樓層,即使下了電梯也要等待電梯移動到該層。

請問從 0 樓到 K 樓的最少時間為何?

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2 30
10 5
0 1 3 5 7 9 11 13 15 20 99
4 13 15 19 20 25 30
2 30
10 1
0 5 10 12 14 20 25 30
2 4 6 8 10 12 14 22 25 28 29
3 50
10 50 100
0 10 30 40
0 20 30
0 20 50
1 1
2
0 2 4 6 8 10

Sample Output

1
2
3
4
1295
600
8505
IMPOSSIBLE

Solution

很明顯地,把每一個樓層當節點,可以根據電梯的移動建造邊,邊與邊之間的轉換必須多 5 花費以及電梯在最慘情況下移動到該層的花費。

電梯在最慘情況下移動到該層的花費 : 電梯在最高樓層或者是最低樓層停靠,收到指令後移動到該層。

直接對其使用最短路即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <sstream>
using namespace std;
struct edge {
int to, v, label;
edge(int a=0, int b=0, int c=0):
to(a), v(b), label(c){}
};
vector<edge> g[128];
int mxfloor[128], mnfloor[128], T[128];
int dist[128], inq[128];
void spfa(int N, int K) {
for (int i = 0; i < 128; i++)
dist[i] = 0x3f3f3f3f;
int u, v, w, l;
queue<int> Q;
Q.push(0), dist[0] = 0;
while (!Q.empty()) {
u = Q.front(), Q.pop();
inq[u] = 0;
for (int i = 0; i < g[u].size(); i++) {
v = g[u][i].to, l = g[u][i].label;
w = g[u][i].v + T[l] * max(mxfloor[l] - u, u - mnfloor[l]) + 5;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
if (!inq[v]) {
inq[v] = 1;
Q.push(v);
}
}
}
}
if (dist[K] == 0x3f3f3f3f)
puts("IMPOSSIBLE");
else
printf("%d\n", K == 0 ? 0 : (dist[K] - 5));
}
int main() {
int N, K, f[128];
char s[1024];
while (scanf("%d %d", &N, &K) == 2) {
for (int i = 0; i < N; i++)
scanf("%d", &T[i]);
for (int i = 0; i < 128; i++)
g[i].clear();
while (getchar() != '\n');
for (int i = 0; i < N; i++) {
gets(s);
stringstream sin(s);
int n = 0;
while (sin >> f[n])
n++;
mxfloor[i] = -1, mnfloor[i] = 0x3f3f3f3f;
for (int j = 0; j < n; j++) {
mxfloor[i] = max(mxfloor[i], f[j]);
mnfloor[i] = min(mnfloor[i], f[j]);
for (int k = 0; k < n; k++) {
if (j == k) continue;
g[f[j]].push_back(edge(f[k], abs(f[k] - f[j]) * T[i], i));
}
}
}
spfa(N, K);
}
return 0;
}
/*
2 30
10 5
0 1 3 5 7 9 11 13 15 20 99
4 13 15 19 20 25 30
2 30
10 1
0 5 10 12 14 20 25 30
2 4 6 8 10 12 14 22 25 28 29
3 50
10 50 100
0 10 30 40
0 20 30
0 20 50
1 1
2
0 2 4 6 8 10
*/