test/simple-dijkstra1.test.cpp

View this file on GitHub
Last update: 2022-12-06 04:57:49+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A"

#include "../src/graph/simple/dijkstra.hpp"
#include "../src/graph/Read-Weighted-Graph.hpp"

int main() {
    int v, e, r; std::cin >> v >> e >> r;
    const long long inf = 1e15;
    auto G = zawa::read_weighted_graph<long long>(v, e, false, false);
    auto table = zawa::dijkstra<long long>(G, r, inf);
    for (auto ans : table) {
        if (ans == inf) {
            std::cout << "INF" << std::endl;
        }
        else {
            std::cout << ans << std::endl;
        }
    }
}

#line 1 "test/simple-dijkstra1.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A"

#line 2 "src/graph/simple/dijkstra.hpp"

#include <vector>
#include <queue>
#include <utility>
#include <limits>

namespace zawa {

template <class cost_type>
std::vector<cost_type> dijkstra(const std::vector<std::vector<std::pair<int, cost_type>>>& G, 
        int s, cost_type inf = std::numeric_limits<cost_type>::max()) {
    std::vector<cost_type> res(G.size(), inf);
    res[s] = 0;
    std::priority_queue<
        std::pair<cost_type, int>, 
        std::vector<std::pair<cost_type, int>>, 
        std::greater<std::pair<cost_type, int>>
            > que;
    que.push({ 0, s }); 
    while (que.size()) {
        auto [d, v] = que.top();
        que.pop();
        if (d > res[v]) {
            continue;
        }
        for (auto [x, w] : G[v]) {
            if (res[x] > d + w) {
                res[x] = d + w;
                que.push({ d + w, x });
            }
        }
    }
    return res;
}

} // namespace zawa
#line 2 "src/graph/Read-Weighted-Graph.hpp"

#line 5 "src/graph/Read-Weighted-Graph.hpp"
#include <iostream>

namespace zawa {

template <typename T>
std::vector<std::vector<std::pair<int, T>>> read_weighted_graph(int n, int m, bool undirect = true, bool minus = true) {
    std::vector<std::vector<std::pair<int, T>>> res(n, std::vector(0, std::pair<int, T>()));
    for (int _ = 0 ; _ < m ; _++) {
        int u, v; std::cin >> u >> v;
        T c; std::cin >> c;
        res[u - minus].emplace_back(v - minus, c);
        if (undirect) {
            res[v - minus].emplace_back(u - minus, c);
        }
    }
    return res;
}

template <typename T>
std::vector<std::vector<std::pair<int, T>>> read_weighted_tree(int n, bool undirect = true) {
    return read_weighted_graph<T>(n, n - 1, undirect);
}

} // namespace zawa
#line 5 "test/simple-dijkstra1.test.cpp"

int main() {
    int v, e, r; std::cin >> v >> e >> r;
    const long long inf = 1e15;
    auto G = zawa::read_weighted_graph<long long>(v, e, false, false);
    auto table = zawa::dijkstra<long long>(G, r, inf);
    for (auto ans : table) {
        if (ans == inf) {
            std::cout << "INF" << std::endl;
        }
        else {
            std::cout << ans << std::endl;
        }
    }
}