題目： UVa - 10449 - Traffic

題目說明

題目看不是很懂，反正就是有一個有向圖，圖上的每個點都有一個數值，邊的權重為 目的地的值 - 出發點的值 的三次方，給一個起點及一些終點，求從起點 ( 1 號點 ) 到終點的最短路徑。

Input： 每組測資的第一個數字 n 表示有 n 個點，後面 n 個數字依序代表點的數值 (1 ~ n)，後面一個整數 m，表示有 m 條邊，後面 m 行每行有兩個整數 u、v，表示有邊 u -> v，後面有一個整數 q，表示有幾個終點，後面 q 個整數表示終點的位置。

Output： 若起點 ( 1 號點 ) 到終點的最短路徑小於 3 或是起點無法到達終點就輸出 "?"，否則輸出最短路徑。

解題思路

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

先建圖並使用 Bellman Ford，之後再做一次，儲存在負環上的點 ( 因為在負環表示可以無限變小 )，之後讀取終點並根據情況輸出即可。

參考解法

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
#include <cmath>
#include <unordered_set>

using namespace std;

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

// data
int busyness[201];
int dist[201];
vector<pair<int, int>> edges[201];
unordered_set<int> s;

void init()
{
    s.clear();
    fill(dist, dist + 201, INT_MAX);
    fill(edges, edges + 201, vector<pair<int, int>>());
}

void bellman(int n)
{
    // 從 1 開始
    dist[1] = 0;

    // 若不存在負環，則做 n - 1 次後 dist 會儲存 0 到每個點的最短路徑
    for (int i = 0; i < n - 1; ++i) for (int u = 1; u <= n; ++u)
    {
        for (auto& [v, w] : edges[u])
            if (dist[u] != INT_MAX) dist[v] = min(dist[u] + w, dist[v]);
    }

    for (int u = 1; u <= n; ++u) for (auto& [v, w] : edges[u])
    {
        // 如果 v 還能變小，表示 v 可以無限變小
        if (dist[u] != INT_MAX && dist[v] > dist[u] + w)
        {
            dist[v] = dist[u] + w;
            s.insert(v);
        }
    }
}

int main()
{
    int n, Case = 0;
    while (cin >> n)
    {
        init();

        for (int i = 1; i <= n; ++i)
        {
            int b;
            cin >> b;
            busyness[i] = b;
        }

        int m;
        cin >> m;

        while (m--)
        {
            int u, v;
            cin >> u >> v;
            edges[u].push_back({ v, (int)pow(busyness[v] - busyness[u], 3) });
        }

        bellman(n);

        int q;
        cin >> q;

        cout << "Set #" << ++Case << '\n';
        while (q--)
        {
            int p;
            cin >> p;
            if (s.count(p) || dist[p] < 3 || dist[p] == INT_MAX) cout << "?\n";
            else cout << dist[p] << '\n';
        }
    }
}