test/library-checker/shortest_path.test.cpp

• View this file on GitHub
• Last update: 2023-03-05 19:05:08+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 <algorithm>
#include <iostream>

#include "graph/dijkstra.hpp"
int main() {
    int n, m, s, t;
    std::cin >> n >> m >> s >> t;
    std::vector<std::vector<std::pair<int, long long>>> g(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        std::cin >> a >> b >> c;
        g[a].emplace_back(b, c);
    }

    auto [dist, from] = dijkstra(s, g);
    if (dist[t] == std::numeric_limits<long long>::max()) {
        std::cout << -1 << '\n';
        return 0;
    }

    int pos = t;
    std::vector<int> path;
    while (pos != -1) {
        path.push_back(pos);
        pos = from[pos];
    };
    std::reverse(path.begin(), path.end());

    std::cout << 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 <algorithm>
#include <iostream>

#line 2 "graph/dijkstra.hpp"
#include <limits>
#include <queue>
#include <vector>
template <typename T>
std::pair<std::vector<T>, std::vector<int>> dijkstra(
    int s, const std::vector<std::vector<std::pair<int, T>>> &g) {
    std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>,
                        std::greater<std::pair<T, int>>>
        que;
    int n = int(g.size());
    std::vector<T> d(n, std::numeric_limits<T>::max());
    std::vector<int> from(n, -1);
    d[s] = 0;
    que.emplace(0, s);
    while (!que.empty()) {
        auto [dist, pos] = que.top();
        que.pop();
        if (d[pos] < dist) continue;
        for (auto [to, cost] : g[pos]) {
            if (d[pos] + cost < d[to]) {
                d[to] = d[pos] + cost;
                from[to] = pos;
                que.emplace(d[to], to);
            }
        }
    }
    return {d, from};
}
#line 6 "test/library-checker/shortest_path.test.cpp"
int main() {
    int n, m, s, t;
    std::cin >> n >> m >> s >> t;
    std::vector<std::vector<std::pair<int, long long>>> g(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        long long c;
        std::cin >> a >> b >> c;
        g[a].emplace_back(b, c);
    }

    auto [dist, from] = dijkstra(s, g);
    if (dist[t] == std::numeric_limits<long long>::max()) {
        std::cout << -1 << '\n';
        return 0;
    }

    int pos = t;
    std::vector<int> path;
    while (pos != -1) {
        path.push_back(pos);
        pos = from[pos];
    };
    std::reverse(path.begin(), path.end());

    std::cout << 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