test/aoj/GRL_1_A.test.cpp

View this file on GitHub
Last update: 2021-02-22 09:25:55+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

Depends on

Code

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

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

using namespace std;
using lint = long long;
constexpr lint LINF = 1LL << 60;

#include "../../src/Dijkstra.hpp"

struct init {
    init() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} init_;

int main() {

    int N, M, s;
    cin >> N >> M >> s;

    vector<vector<Edge<lint>>> edges(N);
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        edges[u].emplace_back(v, c);
    }

    for (const auto &cost : Dijkstra(edges, s)) {
        cout << (cost < LINF ? to_string(cost) : "INF") << '\n';
    }

    return 0;
}

#line 1 "test/aoj/GRL_1_A.test.cpp"

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

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

using namespace std;
using lint = long long;
constexpr lint LINF = 1LL << 60;

#line 2 "src/Dijkstra.hpp"

#line 4 "src/Dijkstra.hpp"
#include <algorithm>
#include <queue>

#line 2 "src/chmin.hpp"

template<class T>
inline bool chmin(T &a, const T b) { return a > b && (a = b, true); }
#line 2 "src/Edge.hpp"

template<class T>
struct Edge {
    int from{}, to{};
    T cost;
    Edge() = default;
    Edge(int to, T cost) : to(to), cost(move(cost)) {}
    Edge(int from, int to, T cost) : from(from), to(to), cost(move(cost)) {}
    bool operator>(const Edge &r) const { return this->cost > r.cost; }
};
#line 9 "src/Dijkstra.hpp"

using namespace std;

template<class T>
vector<T> Dijkstra(const vector<vector<Edge<T>>> &edges, const int st) {

    const int V = (int)edges.size();
    const T inf = numeric_limits<T>::max() / 2;
    vector<T> cost(V, inf);
    cost[st] = 0;

    priority_queue <Edge<T>, vector<Edge<T>>, greater<>> pq;
    pq.emplace(st, cost[st]);

    while (!pq.empty()) {

        Edge<T> now(pq.top().to, pq.top().cost);
        pq.pop();

        if (cost[now.to] < now.cost) continue;
        for (const Edge<T> &e : edges[now.to]) {
            T tmp_cost = now.cost + e.cost;
            if (chmin(cost[e.to], tmp_cost)) {
                pq.emplace(e.to, cost[e.to]);
            }
        }
    }

    return cost; // min cost to vertex idx from st
}
#line 14 "test/aoj/GRL_1_A.test.cpp"

struct init {
    init() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} init_;

int main() {

    int N, M, s;
    cin >> N >> M >> s;

    vector<vector<Edge<lint>>> edges(N);
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        edges[u].emplace_back(v, c);
    }

    for (const auto &cost : Dijkstra(edges, s)) {
        cout << (cost < LINF ? to_string(cost) : "INF") << '\n';
    }

    return 0;
}