UVa 10801 - Lift Hopping

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

從 0 層開始,藉由數台電梯搭到指定樓層,算出所需的最短時間。
每台電梯停的樓層不同,移動所需時間也不同。

Solution

從有到 0 層的電梯開始,如果不只一個就依序放進 priority_queue 。(注意從 0 層開始的耗時為 0 秒)
使用 Dijkstra’s algorithm ,每次更新 目前所選樓層同電梯不同樓層同樓層不同電梯 的最短時間,再用 priority_queue 找出目前離 0 層耗時最少的位置。

Code

UVa 10801UVa 10801 - Lift Hopping
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

#include<cstdio>
#include<queue>
#include<algorithm>
#define N 101
using namespace std;

bool lift[5][N];//[lift][floor]
int t[5];//移動不同樓層的時間
int dijkstra(int tar, int n);
int main()
{
int n, tar;

while (scanf("%d%d", &n, &tar) != EOF)
{
int i;
//init
for (i = 0; i < 5; i++)
fill(lift[i], lift[i] + N, false);

for (i = 0; i < n; i++)
scanf("%d", &t[i]);

//input
getchar();
char str[300];
for (i = 0; i < n; i++)
{
int temp = 0;
gets(str);
for (int j = 0; str[j]; j++)
{
if (str[j] == ' ')
{
lift[i][temp] = true;
temp = 0;
}
else
temp = temp * 10 + str[j] - '0';
}
lift[i][temp] = true;
}


int ans = dijkstra(tar, n);
if (ans == -1)
puts("IMPOSSIBLE");
else
printf("%d\n", ans);
}

return 0;
}
int dijkstra(int tar, int n)
{
int i, j;
struct Floor
{
int id, n, t;
Floor(){}
Floor(int _id, int _n, int _t) :id(_id), n(_n), t(_t){}
bool operator<(const Floor& a)const{ return t>a.t; }//耗時少的較優先
};

bool isVisit[5][N] = {};//[lift][floor]
int T[5][N];//從 0 層到各樓層所需的時間,不同電梯在同樓層的時間也不相同
priority_queue<Floor> PQ;
Floor next;
//init
for (i = 0; i < 5; i++)
fill(T[i], T[i] + N, 1e9);

//有到達 0 層的電梯
for (i = 0; i < n; i++)
if (lift[i][0])
{
T[i][0] = 0;
PQ.push(Floor(i, 0, 0));
}

while (true)
{
next.id = -1;
while (!PQ.empty())
{
next = PQ.top();
PQ.pop();
if (!isVisit[next.id][next.n])
break;
}

isVisit[next.id][next.n] = true;
if (next.id == -1 || next.n == tar)
break;

//更新 next 到同樓層不同電梯的可能最短時間
for (j = 0; j < n; j++)
{
if (lift[j][next.n] && !isVisit[j][next.n])
if (next.t + 60 < T[j][next.n])
{
T[j][next.n] = next.t + 60;
PQ.push(Floor(j, next.n, T[j][next.n]));
}
}

//更新 next 到同電梯不同樓層的可能最短時間
for (j = 0; j < N; j++)
{
if (lift[next.id][j] && !isVisit[next.id][j])
{
//時間計算
int time = t[next.id] * (j - next.n);
if (time < 0)
time *= -1;

if (next.t + time < T[next.id][j])
{
T[next.id][j] = next.t + time;
PQ.push(Floor(next.id, j, T[next.id][j]));
}
}
}
}

return next.n == tar ? next.t : -1;
}