test/Read-Weighted-Graph.test.cpp

• View this file on GitHub
• Last update: 2022-10-26 15:07:24+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/1/GRL_1_A

Depends on

• Read Weighted Graph (重み付きグラフ入力) (src/graph/Read-Weighted-Graph.hpp)

Code

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

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

#include <queue>

int main() {
    int n, m, r; std::cin >> n >> m >> r;
    auto G = zawa::read_weighted_graph<int>(n, m, false, false); 
    std::vector dists(n, (1LL << 60));
    dists[r] = 0;
    std::priority_queue<std::pair<long long, int>> que;
    que.emplace(0LL, r);
    while (que.size()) {
        auto [d, v] = que.top();
        d *= -1;
        que.pop();
        if (d > dists[v]) {
            continue;
        }
        for (auto [x, w] : G[v]) {
            if (d + w < dists[x]) {
                dists[x] = d + w;
                que.emplace(-dists[x], x);
            }
        }
    }
    for (auto d : dists) {
        if (d == (1LL << 60)) {
            std::cout << "INF" << std::endl;
        }
        else {
            std::cout << d << std::endl;
        }
    }
}

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

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

#include <utility>
#include <vector>
#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 4 "test/Read-Weighted-Graph.test.cpp"

#include <queue>

int main() {
    int n, m, r; std::cin >> n >> m >> r;
    auto G = zawa::read_weighted_graph<int>(n, m, false, false); 
    std::vector dists(n, (1LL << 60));
    dists[r] = 0;
    std::priority_queue<std::pair<long long, int>> que;
    que.emplace(0LL, r);
    while (que.size()) {
        auto [d, v] = que.top();
        d *= -1;
        que.pop();
        if (d > dists[v]) {
            continue;
        }
        for (auto [x, w] : G[v]) {
            if (d + w < dists[x]) {
                dists[x] = d + w;
                que.emplace(-dists[x], x);
            }
        }
    }
    for (auto d : dists) {
        if (d == (1LL << 60)) {
            std::cout << "INF" << std::endl;
        }
        else {
            std::cout << d << std::endl;
        }
    }
}

Back to top page