tests/graph/dijkstra.test.cpp

View this file on GitHub
Last update: 2024-04-03 22:46:30+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

Depends on

Code

#include <bits/stdc++.h>
#include "ugilib/graph/dijkstra.hpp"

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp"

using namespace std;

int main() {
    // speed up io
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    // code
    ll V, E, r;
    cin >> V >> E >> r;

    vector<vector<pair<int, ll>>> graph(V);

    rep(i, E) {
        int s, t, d;
        cin >> s >> t >> d;
        graph[s].push_back({t, d});
    }

    auto &&costs = ugilib::dijkstra(V, r, graph, ugilib::constants::INF<ll>);
    rep(i, V) {
        if (costs[i] == INF) cout << "INF\n";
        else cout << costs[i] << '\n';
    }

    return 0;
}

#line 1 "tests/graph/dijkstra.test.cpp"
#include <bits/stdc++.h>
#line 2 "ugilib/base/definitions.hpp"

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define rep(i, n) for(size_t i = 0; i < n; i++)  // rep macro
#define all(v) begin(v), end(v)  // all iterator
#line 3 "ugilib/base/constants.hpp"

namespace ugilib::constants {
    template<typename T>
    inline constexpr T INF = std::numeric_limits<T>::max() / 2;
} // namespace ugilib::constants

const ll INF = ugilib::constants::INF<ll>;
#line 4 "ugilib/graph/dijkstra.hpp"

using namespace std;

namespace ugilib {
    /**
     * @brief ダイクストラ法
     * @param n グラフの頂点数
     * @param start 始点
     * @param graph グラフ. vector<pair<int, weight_t>> で隣接頂点とコストを表す
     * @param weight_inf 無限大の値. パスが存在しない場合のコスト
     * @return 始点から各頂点までの最短距離
     * @note O((E+V)logV)
    */
    template<typename weight_t>
    vector<weight_t> dijkstra(int n, int start, const vector<vector<pair<int, weight_t>>>& graph, const weight_t weight_inf = ugilib::constants::INF<weight_t>) {
        vector<weight_t> costs(n, weight_inf);
        costs[start] = 0;

        priority_queue<pair<weight_t, int>, vector<pair<weight_t, int>>, greater<>> next_nodes;
        next_nodes.push({0, start});

        while (!next_nodes.empty()) {
            auto [cost, node] = next_nodes.top(); next_nodes.pop();
            if (cost > costs[node]) continue;

            for (const auto [next_node, next_cost] : graph[node]) {
                auto new_cost = cost + next_cost;
                if (new_cost < costs[next_node]) {
                    costs[next_node] = new_cost;
                    next_nodes.push({costs[next_node], next_node});
                }
            }
        }

        return costs;
    }
} // namespace ugilib
#line 3 "tests/graph/dijkstra.test.cpp"

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp"

using namespace std;

int main() {
    // speed up io
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    // code
    ll V, E, r;
    cin >> V >> E >> r;

    vector<vector<pair<int, ll>>> graph(V);

    rep(i, E) {
        int s, t, d;
        cin >> s >> t >> d;
        graph[s].push_back({t, d});
    }

    auto &&costs = ugilib::dijkstra(V, r, graph, ugilib::constants::INF<ll>);
    rep(i, V) {
        if (costs[i] == INF) cout << "INF\n";
        else cout << costs[i] << '\n';
    }

    return 0;
}