解題區/解題區 - 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
*/