test/library-checker/shortest_path.test.cpp

• View this file on GitHub
• Last update: 2026-10-20 08:03:47+09:00
• Problem: https://judge.yosupo.jp/problem/shortest_path

Depends on

• Dijkstra 法 (graph/dijkstra.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path"
#include <iostream>

#include "graph/dijkstra.hpp"
int main() {
    int n, m, s, t;
    std::cin >> n >> m >> s >> t;
    dijkstra<long long> d(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        std::cin >> a >> b >> c;
        d.add_edge(a, b, c);
    }
    d.solve(s);
    if (!d.reachable(t)) {
        std::cout << -1 << '\n';
        return 0;
    }
    std::vector<int> path = d.path(t);
    std::cout << d.dist(t) << ' ' << path.size() - 1 << '\n';
    for (int i = 0; i + 1 < int(path.size()); i++) {
        std::cout << path[i] << ' ' << path[i + 1] << '\n';
    }
}

#line 1 "test/library-checker/shortest_path.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path"
#include <iostream>

#line 2 "graph/dijkstra.hpp"
#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <vector>
template <class T> struct dijkstra {
public:
    dijkstra() : dijkstra(0) {
    }
    explicit dijkstra(int n) : _n(n), g(n), _dist(n, inf), _prev(n, -1) {
    }
    void add_edge(int from, int to, T w) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        g[from].emplace_back(to, w);
    }
    void solve(int s) {
        assert(0 <= s && s < _n);
        _dist.assign(_n, inf);
        _prev.assign(_n, -1);
        std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>,
                            std::greater<std::pair<T, int>>>
            que;
        _dist[s] = 0;
        que.emplace(0, s);
        while (!que.empty()) {
            auto [d, u] = que.top();
            que.pop();
            if (_dist[u] < d) continue;
            for (auto [v, w] : g[u]) {
                if (_dist[u] + w < _dist[v]) {
                    _dist[v] = _dist[u] + w;
                    _prev[v] = u;
                    que.emplace(_dist[v], v);
                }
            }
        }
    }
    T dist(int v) const {
        assert(0 <= v && v < _n);
        return _dist[v];
    }
    int prev(int v) const {
        assert(0 <= v && v < _n);
        return _prev[v];
    }
    bool reachable(int v) const {
        assert(0 <= v && v < _n);
        return _dist[v] != inf;
    }
    std::vector<int> path(int t) const {
        assert(0 <= t && t < _n);
        if (_dist[t] == inf) return {};
        std::vector<int> res;
        for (int v = t; v != -1; v = _prev[v]) res.push_back(v);
        std::reverse(res.begin(), res.end());
        return res;
    }

private:
    static constexpr T inf = std::numeric_limits<T>::max();
    int _n;
    std::vector<std::vector<std::pair<int, T>>> g;
    std::vector<T> _dist;
    std::vector<int> _prev;
};
#line 5 "test/library-checker/shortest_path.test.cpp"
int main() {
    int n, m, s, t;
    std::cin >> n >> m >> s >> t;
    dijkstra<long long> d(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        std::cin >> a >> b >> c;
        d.add_edge(a, b, c);
    }
    d.solve(s);
    if (!d.reachable(t)) {
        std::cout << -1 << '\n';
        return 0;
    }
    std::vector<int> path = d.path(t);
    std::cout << d.dist(t) << ' ' << path.size() - 1 << '\n';
    for (int i = 0; i + 1 < int(path.size()); i++) {
        std::cout << path[i] << ' ' << path[i + 1] << '\n';
    }
}

Back to top page