uva10986: Dijkstra

uva10986.md

UVA 10986

題目

分析

祼最短路徑，可用來驗證程式碼的正確性。

priority_queue 預設是比較次序大的在前面，但我們希望小的（cost 小的）在前面，可用以下任一方法來實現：

1. 改用 greater<T> ，並對 > 運算子重載，而非 <。
2. 直接改寫比較函式，但不建議，因與邏輯相反。

AC Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>

using namespace std;

struct Edge {
    int to;
    int cost;

    bool operator > (const Edge& e) const {
        return cost > e.cost;
    }
};

int dijkstra(const vector<vector<Edge>>& graph, int S, int T) {
    const int N = graph.size();
    priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
    int d[N];
    fill(d, d + N, 1000000000);

    pq.push(Edge{S, 0});
    d[S] = 0;

    while (!pq.empty()) {
        Edge top = pq.top();
        pq.pop();
        int v = top.to;

        if (top.cost > d[v])
            continue;

        if (v == T)
            break;

        for (size_t i = 0; i < graph[v].size(); i++) {
            Edge e = graph[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                pq.push(Edge{e.to, d[e.to]});
            }
        }
    }

    if (d[T] == 1000000000)
        return -1;
    return d[T];
}

int main() {
    ios::sync_with_stdio(false);

    int T;
    cin >> T;

    for (int case_ = 1; case_ <= T; case_++) {
        int N, M, S, T;
        cin >> N >> M >> S >> T;

        vector<vector<Edge>> graph(N);
        while (M--) {
            int a, b, w;
            cin >> a >> b >> w;

            graph[a].push_back(Edge{b, w});
            graph[b].push_back(Edge{a, w});
        }

        int ans = dijkstra(graph, S, T);

        cout << "Case #" << case_ << ": ";
        if (ans == -1)
            cout << "unreachable\n";
        else
            cout << ans << "\n";
    }

    return 0;
}