題目： UVa - 1112 - Mice and Maze

題目說明

給一張有向圖，走過每條邊都需要一些時間，從圖上任意點走需要最少時間的路徑到終點，求有多少點可以在限定的時間內走到。

Input： 第一行為一個整數，表示有幾組測資，每組測資一開始有四個整數 n、end、time、m，表示 有 n 個點 (1 ~ n)、終點為 end、限定時間為 time、有 m 條邊。後面 m 行，每行有 3 個整數 u、v、w，表示有邊可以從 u 走到 v，需要的時間為 w。

Output： 求有多少點可以在限定的時間內走到終點。需要注意的是，終點本身也算一個點。

解題思路

這個解法需要有 Dijkstra 演算法的概念。

若模擬從每個點開始，會非常沒效率，所以我們可以將題目轉換一下，將圖上的所有邊反向，從終點開始，走到圖上各點花費的時間跟從各點走到終點是一樣的，這樣只需要做一次就可以了。

使用 Dijkstra 搭配 Priority_queue 求解即可。

參考解法

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
#include <iostream>
#include <climits>
#include <queue>
#include <unordered_map>

using namespace std;

// reference: https://ppt.cc/fU8XZx

static auto __ = []
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

struct point
{
    int v;
    int w;

    bool operator>(const point& r) const { return w > r.w; }
};

// data
unordered_map<int, vector<pair<int, int>>> edges;
int value[101];
bool visited[101];
priority_queue<point, vector<point>, greater<point>> pq;

void init(int n)
{
    edges.clear();
    for (int i = 1; i <= n; ++i) value[i] = INT_MAX, visited[i] = false;
}

void dijkstra(int start)
{
    pq.push({ start, value[start] = 0 });

    while (!pq.empty())
    {
        auto [u, val] = pq.top();
        visited[u] = true;
        pq.pop();

        for (auto& [v, w] : edges[u])
        {
            if (visited[v]) continue;
            int tmp = val + w;
            if (value[v] > tmp) pq.push({ v, value[v] = tmp });
        }
    }
}

int main()
{
    int T;
    cin >> T;
    
    while (T--)
    {
        int n, end, time, m;
        cin >> n >> end >> time >> m;
        init(n);
        
        while (m--)
        {
            int u, v, w;
            cin >> u >> v >> w;

            // 反向建邊
            edges[v].push_back({ u, w });
        }

        // 從終點開始
        dijkstra(end);

        int ret = 0;
        for (int i = 1; i <= n; ++i) if (value[i] <= time) ++ret;

        cout << ret << '\n';
        if (T) cout << '\n';
    }
}

參考資料

[題解] UVa 1112 - Mice and Maze