test/dijkstra.test.cpp

View this file on GitHub
Last update: 2024-04-20 19:36:17+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

Depends on

graph/dijkstra.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A"
#include <bits/stdc++.h>
#include "../graph/dijkstra.hpp"
using namespace std;

int main() {
    int n, m, r;
    cin >> n >> m >> r;
    vector<vector<Edge>> g(n), inv(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        inv[b].push_back({a, c});
    }
    vector<long long> dist = dijkstra(g, r);
    for (int i = 0; i < n; i++) {
        if (dist[i] == 1LL << 60) cout << "INF" << endl;
        else cout << dist[i] << endl;
    }
}

#line 1 "test/dijkstra.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A"
#include <bits/stdc++.h>
#line 3 "graph/dijkstra.hpp"
using namespace std;

struct Edge {
    int to, cost;
};

// 1LL << 60 if infty
vector<long long> dijkstra(vector<vector<Edge>> g, int s) {
    vector<long long> ret((int) g.size(), 1LL << 60);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
    q.push({0, s});
    ret[s] = 0;
    while (!q.empty()) {
        pair<long long, int> p = q.top(); q.pop();
        long long &dist = p.first;
        int &v = p.second;
        if (ret[v] < dist) continue;
        ret[v] = dist;
        for (Edge &e : g[v]) {
            if (ret[e.to] > dist + e.cost) {
                ret[e.to] = dist + e.cost;
                q.push({dist + e.cost, e.to});
            }
        }
    }
    return ret;
}
#line 4 "test/dijkstra.test.cpp"
using namespace std;

int main() {
    int n, m, r;
    cin >> n >> m >> r;
    vector<vector<Edge>> g(n), inv(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        inv[b].push_back({a, c});
    }
    vector<long long> dist = dijkstra(g, r);
    for (int i = 0; i < n; i++) {
        if (dist[i] == 1LL << 60) cout << "INF" << endl;
        else cout << dist[i] << endl;
    }
}