解題區►解題區 - UVa

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
*/