Test/AOJ/GRL_1_A.test.cpp

View this file on GitHub
Last update: 2023-08-04 19:12:51+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/Template/TypeAlias.hpp"
#include "../../Src/Template/Chmin.hpp"

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace zawa;

int main() {
    usize N, M; std::cin >> N >> M;
    u32 r; std::cin >> r;
    std::vector<std::vector<std::pair<u32, u32>>> G(N);
    for (u32 _{} ; _ < M ; _++) {
        u32 u, v, c; std::cin >> u >> v >> c;
        G[u].emplace_back(v, c);
    }

    const u64 inf{(1LL << 60)};
    std::vector<u64> dist(N, inf);
    dist[r] = 0;
    using qt = std::pair<u64, u32>;
    std::priority_queue<qt, std::vector<qt>, std::greater<qt>> que;
    que.emplace(0LL, r);
    while (que.size()) {
        auto [d, v]{ que.top() };
        que.pop();
        if (dist[v] < d) continue;
        for (auto [x, w] : G[v]) {
            if (Chmin(dist[x], d + w)) {
                que.emplace(dist[x], x);
            }
        }
    }

    for (auto d : dist) {
        if (d == inf) std::cout << "INF" << std::endl;
        else std::cout << d << std::endl;
    }
}

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

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 2 "Src/Template/Chmin.hpp"

namespace zawa {

template <class T1, class T2>
bool Chmin(T1& fr, const T2& bk) {
    return fr > bk and (fr = bk, true);
}

} // namespace zawa
#line 5 "Test/AOJ/GRL_1_A.test.cpp"

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace zawa;

int main() {
    usize N, M; std::cin >> N >> M;
    u32 r; std::cin >> r;
    std::vector<std::vector<std::pair<u32, u32>>> G(N);
    for (u32 _{} ; _ < M ; _++) {
        u32 u, v, c; std::cin >> u >> v >> c;
        G[u].emplace_back(v, c);
    }

    const u64 inf{(1LL << 60)};
    std::vector<u64> dist(N, inf);
    dist[r] = 0;
    using qt = std::pair<u64, u32>;
    std::priority_queue<qt, std::vector<qt>, std::greater<qt>> que;
    que.emplace(0LL, r);
    while (que.size()) {
        auto [d, v]{ que.top() };
        que.pop();
        if (dist[v] < d) continue;
        for (auto [x, w] : G[v]) {
            if (Chmin(dist[x], d + w)) {
                que.emplace(dist[x], x);
            }
        }
    }

    for (auto d : dist) {
        if (d == inf) std::cout << "INF" << std::endl;
        else std::cout << d << std::endl;
    }
}