Graph/tests/dijkstra.test.cpp

• View this file on GitHub
• Last update: 2022-12-26 16:37:58+08:00
• Problem: https://judge.yosupo.jp/problem/shortest_path

Depends on

• Graph/dijkstra.h

Code

#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path"

#include <bits/stdc++.h>
using namespace std;

#include "../dijkstra.h"

#define SZ(x) ((int)(x).size())
#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, s, t; cin >> n >> m >> s >> t;

    // read edges
    vector<vector<pair<int,ll>>> g(n);
    while (m--) {
        int u, v, c; cin >> u >> v >> c;
        g[u].push_back({v, c});
    }

    // output
    auto [dist, path] = dijkstra(g, s, t);
    if (dist == INF) {
        cout << -1 << endl;
        return 0;
    }

    cout << dist << ' ' << SZ(path) - 1 << '\n';
    REP(i,SZ(path)-1) {
        cout << path[i] << ' ' << path[i+1] << '\n';
    }
    return 0;
}

#line 1 "Graph/tests/dijkstra.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path"

#include <bits/stdc++.h>
using namespace std;

#line 1 "Graph/dijkstra.h"
// Dijkstra
//
// Notes:
// - Index from 0
//
// Tested:
// - https://judge.yosupo.jp/problem/shortest_path
//
// Param:
// - g[u] = pair<v, cost>, adjacency list
// - start = start vertex
// Returns:
// - distances from start. If unreachable -> dist = INF
// - previous vertex. Previous[start] = start. If unreachable -> trace = -1
// Dijkstra {{{
using ll = long long;
const ll INF = 1e18;  // must be greater than maximum possible path
pair<vector<ll>, vector<int>> dijkstra(const vector<vector<pair<int, ll>>>& g, int start) {
    int n = g.size();
    vector<ll> f(n, INF);
    vector<int> trace(n, -1);
    f[start] = 0;
    trace[start] = start;
    using P = pair<ll, int>;  // <distance, vertex>

    // priority_queue should be faster than set?
    priority_queue<P, vector<P>, greater<P>> all;
    all.push(P{0LL, start});
    while (!all.empty()) {
        auto [dist, u] = all.top();
        all.pop();
        if (dist != f[u]) continue;

        for (auto [v, c] : g[u]) {
            if (f[v] > f[u] + c) {
                f[v] = f[u] + c;
                trace[v] = u;
                all.push(P{f[v], v});
            }
        }
    }

    return {f, trace};
}

// Dijkstra from start -> target
// Returns:
// - distance. If unreachable -> INF
// - path. If unreachable -> {}
pair<ll, vector<int>> dijkstra(const vector<vector<pair<int, ll>>>& g, int start, int target) {
    auto [f, trace] = dijkstra(g, start);
    if (trace[target] < 0) {
        return {INF, {}};
    }

    vector<int> path;
    for (int u = target; u != start; u = trace[u]) {
        path.push_back(u);
    }
    path.push_back(start);
    reverse(path.begin(), path.end());
    return {f[target], path};
}
// }}}
#line 7 "Graph/tests/dijkstra.test.cpp"

#define SZ(x) ((int)(x).size())
#define REP(i, a) for (int i = 0, _##i = (a); i < _##i; ++i)

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, s, t; cin >> n >> m >> s >> t;

    // read edges
    vector<vector<pair<int,ll>>> g(n);
    while (m--) {
        int u, v, c; cin >> u >> v >> c;
        g[u].push_back({v, c});
    }

    // output
    auto [dist, path] = dijkstra(g, s, t);
    if (dist == INF) {
        cout << -1 << endl;
        return 0;
    }

    cout << dist << ' ' << SZ(path) - 1 << '\n';
    REP(i,SZ(path)-1) {
        cout << path[i] << ' ' << path[i+1] << '\n';
    }
    return 0;
}

Back to top page