test/graph/dijkstra.test.cpp

• View this file on GitHub
• Last update: 2026-03-02 14:25:31+09:00
• Problem: https://judge.yosupo.jp/problem/shortest_path
• Link: View error logs on GitHub Actions

Depends on

• graph/csr_graph.hpp

Code

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

#include "graph/csr_graph.hpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int n, m, s, t;
    std::cin >> n >> m >> s >> t;
    CSRGraph<std::monostate, long long> g(n);
    for (auto i = 0; i < m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        g.add_edge(u, v, w);
    }
    g.build_directed();
    using S = std::pair<long long, int>;
    std::vector<int> parent(n, -1);
    std::vector<long long> dist(n, std::numeric_limits<long long>::max());
    std::priority_queue<S, std::vector<S>, std::greater<>> pq;
    dist[s] = 0;
    pq.emplace(dist[s], s);
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) {
            continue;
        }
        for (auto [v, w] : g[u]) {
            if (d + w < dist[v]) {
                parent[v] = u;
                dist[v] = d + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    if (dist[t] == std::numeric_limits<long long>::max()) {
        std::cout << -1;
    } else {
        std::vector<int> ans;
        for (auto u = t; u != s; u = parent[u]) {
            ans.push_back(u);
        }
        auto X = dist[t];
        auto Y = (int)ans.size();
        ans.push_back(s);
        std::cout << X << " " << Y << "\n";
        for (auto i = Y; 0 < i; --i) {
            std::cout << ans[i] << " " << ans[i - 1] << "\n";
        }
    }
}

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

#line 1 "graph/csr_graph.hpp"



#include <cassert>
#include <ranges>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>

template <typename EdgeWeight = std::monostate, typename NodeWeight = std::monostate>
struct CSRGraph {
    static constexpr bool HasNodeWeight = !std::is_same_v<NodeWeight, std::monostate>;
    CSRGraph(int n) : n_(n), start_(n + 1) {
        if constexpr (HasNodeWeight) {
            nodes_.resize(n_);
        }
    }
    void set_node(int u, NodeWeight w) {
        assert(0 <= u && u < n_);
        if constexpr (HasNodeWeight) {
            nodes_[u] = w;
        }
    }
    NodeWeight node_weight(int u) const {
        assert(0 <= u && u < n_);
        if constexpr (HasNodeWeight) {
            return nodes_[u];
        } else {
            return {};
        }
    }
    void add_edge(int u, int v, EdgeWeight w = {}) {
        assert(0 <= u && u < n_ && 0 <= v && v < n_);
        raw_edges_.push_back({u, v, w});
    }
    void build_undirected() {
        assert(!built_);
        edges_.resize(2 * raw_edges_.size());
        for (const auto &e : raw_edges_) {
            ++start_[e.u + 1];
            ++start_[e.v + 1];
        }
        for (int i = 0; i < n_; ++i) {
            start_[i + 1] += start_[i];
        }
        auto counter = start_;
        for (const auto &e : raw_edges_) {
            edges_[counter[e.u]++] = {e.v, e.w};
            edges_[counter[e.v]++] = {e.u, e.w};
        }
        std::vector<RawEdge>().swap(raw_edges_);
        built_ = true;
    }
    void build_directed() {
        assert(!built_);
        edges_.resize(raw_edges_.size());
        for (const auto &e : raw_edges_) {
            ++start_[e.u + 1];
        }
        for (int i = 0; i < n_; ++i) {
            start_[i + 1] += start_[i];
        }
        auto counter = start_;
        for (const auto &e : raw_edges_) {
            edges_[counter[e.u]++] = {e.v, e.w};
        }
        std::vector<RawEdge>().swap(raw_edges_);
        built_ = true;
    }
    auto operator[](int u) const {
        assert(built_);
        assert(0 <= u && u < n_);
        constexpr auto f = [](Edge e) { return std::pair(e.to, e.w); };
        return std::ranges::subrange(edges_.begin() + start_[u], edges_.begin() + start_[u + 1]) |
               std::views::transform(f);
    }
    int size() const { return n_; }
    struct Edge {
        int to;
        [[no_unique_address]] EdgeWeight w;
    };
    struct RawEdge {
        int u, v;
        [[no_unique_address]] EdgeWeight w;
    };
    int n_;
    bool built_ = false;
    std::vector<Edge> edges_;
    std::vector<int> start_;
    std::vector<RawEdge> raw_edges_;
    std::vector<NodeWeight> nodes_;
};


#line 4 "test/graph/dijkstra.test.cpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int n, m, s, t;
    std::cin >> n >> m >> s >> t;
    CSRGraph<std::monostate, long long> g(n);
    for (auto i = 0; i < m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        g.add_edge(u, v, w);
    }
    g.build_directed();
    using S = std::pair<long long, int>;
    std::vector<int> parent(n, -1);
    std::vector<long long> dist(n, std::numeric_limits<long long>::max());
    std::priority_queue<S, std::vector<S>, std::greater<>> pq;
    dist[s] = 0;
    pq.emplace(dist[s], s);
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) {
            continue;
        }
        for (auto [v, w] : g[u]) {
            if (d + w < dist[v]) {
                parent[v] = u;
                dist[v] = d + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    if (dist[t] == std::numeric_limits<long long>::max()) {
        std::cout << -1;
    } else {
        std::vector<int> ans;
        for (auto u = t; u != s; u = parent[u]) {
            ans.push_back(u);
        }
        auto X = dist[t];
        auto Y = (int)ans.size();
        ans.push_back(s);
        std::cout << X << " " << Y << "\n";
        for (auto i = Y; 0 < i; --i) {
            std::cout << ans[i] << " " << ans[i - 1] << "\n";
        }
    }
}

Back to top page