test/dijkstra.test.cpp

• View this file on GitHub
• Last update: 2022-10-23 13:46:28+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A

Depends on

• graph/dijkstra.cpp

Code

#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A"
#include "../graph/dijkstra.cpp"
#include "../template/const.hpp"

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    Dijkstra<int, INF> dij(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dij.add_edge(a, b, c);
    }

    auto dist = dij.solve(s);
    for (auto &a : dist) {
        if (a == INF)
            cout << "INF\n";
        else
            cout << a << '\n';
    }
    return 0;
}

#line 1 "test/dijkstra.test.cpp"
#include <bits/stdc++.h>
using namespace std;

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A"
#line 3 "graph/dijkstra.cpp"
using namespace std;

// Dijkstra
// dijkstra法で最短経路を求める.
template <typename T, const T INF>
struct Dijkstra {
    using edge = pair<T, int>;
    int n;

    vector<vector<edge>> G;
    vector<T> dist;
    vector<int> prev;
    Dijkstra(int n) : n(n) {
        G.resize(n);
        dist.resize(n);
        prev.resize(n);
    }

    // add_edge
    // aからbへコストcの辺を張る
    // 制約: c >= 0
    void add_edge(int a, int b, T c) {
        G[a].emplace_back(c, b);
    }

    // solve
    // sからの最短経路を求める.
    // 計算量: O(|E|log|V|)
    vector<T> solve(int s = 0) {
        fill(dist.begin(), dist.end(), INF);
        fill(prev.begin(), prev.end(), -1);
        dist[s] = 0;

        priority_queue<edge, vector<edge>, greater<edge>> q;
        q.push({0, s});

        while (!q.empty()) {
            edge p = q.top();
            q.pop();
            auto [d, v] = p;
            if (dist[v] < d) continue;
            for (const auto &p : G[v]) {
                auto [cost, u] = p;
                if (dist[u] > dist[v] + cost) {
                    dist[u] = dist[v] + cost;
                    prev[u] = v;
                    q.push({dist[u], u});
                }
            }
        }
        return dist;
    }

    // restore_path
    // 頂点sからtまでの最短経路を求める。
    // 最短経路が存在する場合, 返り値は先頭にs,tを含む. 存在しないとき空を返す.
    // 制約: sは以前にsolve(s)が呼ばれている. 0 <= t < n
    vector<int> restore_path(int s, int t) {
        if (dist[t] == INF) return {};

        vector<int> ret;
        int now_v = t;
        ret.push_back(now_v);
        while (now_v != s) {
            now_v = prev[now_v];
            ret.push_back(now_v);
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
};
#line 2 "template/const.hpp"
constexpr int INF        = 1000'000'000;
constexpr long long HINF = 4000'000'000'000'000'000;
constexpr long long MOD  = 998244353;
constexpr double EPS     = 1e-6;
constexpr double PI      = 3.14159265358979;
#line 7 "test/dijkstra.test.cpp"

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    Dijkstra<int, INF> dij(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        dij.add_edge(a, b, c);
    }

    auto dist = dij.solve(s);
    for (auto &a : dist) {
        if (a == INF)
            cout << "INF\n";
        else
            cout << a << '\n';
    }
    return 0;
}

Back to top page