Problem Solving►UVa

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;
}