test/Graph/dijkstra_Shortest_Path.test.cpp

View this file on GitHub
Last update: 2023-11-13 00:21:55+09:00
Problem: https://judge.yosupo.jp/problem/shortest_path

Depends on

Code

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

#include <iostream>
#include <vector>

#include "../../src/Graph/dijkstra.hpp"

int main() {
    int N, M, s, t;
    std::cin >> N >> M >> s >> t;
    lib::Graph<long long> G(N);

    for (int i = 0; i < M; i++) {
        int a, b;
        long long c;
        std::cin >> a >> b >> c;
        G.add_edge(a, b, c);
    }

    auto dist = lib::dijkstra(s, G);
    std::vector<int> path;
    long long X = dist[t].first;
    if (X == std::numeric_limits<long long>::max()) {
        std::cout << -1 << '\n';
        return 0;
    }

    while (dist[t].second != -1) {
        path.push_back(t);
        t = dist[t].second;
    }
    path.push_back(s);
    int Y = (int)path.size() - 1;
    std::cout << X << ' ' << Y << '\n';
    for (int i = Y; i > 0; i--) {
        std::cout << path[i] << ' ' << path[i - 1] << '\n';
    }
}

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

#include <iostream>
#include <vector>

#line 2 "src/Graph/dijkstra.hpp"

#include <cassert>
#include <limits>
#include <queue>
#line 7 "src/Graph/dijkstra.hpp"

#line 2 "src/Graph/Graph.hpp"

#line 7 "src/Graph/Graph.hpp"

namespace lib {
template <class T>
struct Edge {
   public:
    Edge() : _to(-1), _cost(0) {}
    Edge(int to, T cost = 1) : _to(to), _cost(cost) {}
    int to() { return _to; }
    T cost() { return _cost; }
    void change_cost(const T& val) { _cost = val; }
    void change_to(const int& val) { _to = val; }

   private:
    int _to;
    T _cost;
};

template <class T = long long>
class Graph {
   public:
    Graph(int N) : N(N), G(N) {}
    void add_edge(int u, int v, T cost = 1) {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        G[u].push_back(Edge<T>(v, cost));
        return;
    }

    void erase_edge(int u, int idx) {
        assert(0 <= u && u < N);
        assert(0 <= idx && idx < (int)G[u].size());
        swap_edge(G[u][idx], G[u].back());
        G[u].pop_back();
        return;
    }

    void erase_edge_vertex(int u, int v) {
        assert(0 <= u && u < N);
        assert(0 <= v && v < N);
        int last = (int)(G[u].size() - 1);
        for (int i = 0; i < (int)(G[u].size()); i++) {
            if (i > last) {
                break;
            }
            if (G[u][i].to() == v) {
                swap_edge(G[u][i], G[u][last]);
                last--;
            }
        }

        for (int i = last; i < (int)(G[u].size()); i++) {
            G[u][i].pop_back();
        }
        return;
    }

    const std::vector<Edge<T>>& operator[](int i) const {
        assert(0 <= i && i < N);
        return G[i];
    }

    std::size_t size() const { return G.size(); }

   private:
    const int N;
    std::vector<std::vector<Edge<T>>> G;
    void swap_edge(Edge<T>& e1, Edge<T>& e2) {
        int to1 = e1.to();
        e1.change_to(e2.to());
        e2.change_to(to1);

        T cost1 = e1.cost;
        e1.change_cost(e2.cost());
        e2.change_ost(cost1);
        return;
    }
};
}  // namespace lib
#line 9 "src/Graph/dijkstra.hpp"

namespace lib {
template <class T = long long>
std::vector<std::pair<T, int>> dijkstra(int start, const Graph<T>& G,
                                        T start_val = 0) {
    assert(0 <= start && start < (int)G.size());
    // 距離 と どこからかを保持
    std::vector<std::pair<T, int>> dist(
        (int)G.size(), std::make_pair(std::numeric_limits<T>::max(), -1));
    std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>,
                        std::greater<std::pair<T, int>>>
        que;
    que.push(std::make_pair(start_val, start));
    dist[start].first = start_val;
    while (!que.empty()) {
        T dist_q = que.top().first, vertex = que.top().second;
        que.pop();
        if (dist[vertex].first < dist_q) {
            continue;
        }
        for (Edge<T> edge : G[vertex]) {
            // dist[vertex] is not max()
            if (dist[edge.to()].first > dist[vertex].first + edge.cost()) {
                dist[edge.to()].first = dist[vertex].first + edge.cost();
                dist[edge.to()].second = vertex;
                que.push(std::make_pair(dist[edge.to()].first, edge.to()));
            }
        }
    }

    return dist;
}
}  // namespace lib
#line 7 "test/Graph/dijkstra_Shortest_Path.test.cpp"

int main() {
    int N, M, s, t;
    std::cin >> N >> M >> s >> t;
    lib::Graph<long long> G(N);

    for (int i = 0; i < M; i++) {
        int a, b;
        long long c;
        std::cin >> a >> b >> c;
        G.add_edge(a, b, c);
    }

    auto dist = lib::dijkstra(s, G);
    std::vector<int> path;
    long long X = dist[t].first;
    if (X == std::numeric_limits<long long>::max()) {
        std::cout << -1 << '\n';
        return 0;
    }

    while (dist[t].second != -1) {
        path.push_back(t);
        t = dist[t].second;
    }
    path.push_back(s);
    int Y = (int)path.size() - 1;
    std::cout << X << ' ' << Y << '\n';
    for (int i = Y; i > 0; i--) {
        std::cout << path[i] << ' ' << path[i - 1] << '\n';
    }
}