VvyLw's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub

:heavy_check_mark: test/shortestpath.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path"
#include <iostream>
#include "C++/graph/WeightedGraph.hpp"
int main() {
    int n, m, s, t;
    std::cin >> n >> m >> s >> t;
    w_graph<false> g(n, 0);
    g.input(m);
    auto dj = g.dijkstra(s);
    if(!dj.is_thru(t)) {
        std::cout << "-1\n";
        return 0;
    }
    const auto ed = dj.path(t);
    std::cout << dj.get()[t] << ' ';
    const int len = ed.size() - 1;
    std::cout << len << '\n';
    for(int i = 0; i < len; ++i) {
        std::cout << ed[i] << ' ' << ed[i + 1] << '\n';
    }
}
#line 1 "test/shortestpath.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path"
#include <iostream>
#line 2 "C++/graph/WeightedGraph.hpp"

#line 2 "C++/graph/Graph.hpp"

#line 4 "C++/graph/Graph.hpp"
#include <vector>

#include <algorithm>

#include <queue>

#include <stack>

#ifndef TEMPLATE
template <class T, class U> bool chmin(T& a, const U& b){ if(a>b){ a=b; return 1; } return 0; }
#endif
#line 2 "C++/graph/edge.hpp"

struct edge {
    int src, to, id;
    long long cost;
    edge(){}
    edge(const int src_, const int to_, const int id_ = -1, const long long cost_ = 0): src(src_), to(to_), id(id_), cost(cost_){}
    operator int() const { return to; }
};

/**
 * @brief Edge
 */
#line 12 "C++/graph/Graph.hpp"
template <bool undirected = true> struct graph: std::vector<std::vector<edge>> {
protected:
    int indexed, id;
    std::vector<edge> edges;
public:
    graph(){}
    graph(const int n, const int indexed_ = 1): indexed(indexed_), id(0){ this -> resize(n); }
    void add(int a, int b) {
        a -= indexed, b-= indexed;
        (*this)[a].emplace_back(a, b, id);
        edges.emplace_back(a, b, id++);
        if(undirected) {
            (*this)[b].emplace_back(b, a, --id);
            edges.emplace_back(b, a, id++);
        }
    }
    void input(const int m) {
        for(int i = 0; i < m; ++i) {
            int a, b;
            std::cin >> a >> b;
            add(a, b);
        }
    }
    std::vector<edge> get_edge() const { return edges; }
    std::vector<int> all_dist(const int v) {
        std::vector<int> d(this -> size(), -1);
        std::queue<int> q;
        d[v] = 0;
        q.emplace(v);
        while(q.size()) {
            const int tmp = q.front();
            q.pop();
            for(const auto &el: (*this)[tmp]) {
                if(d[el] != -1) {
                    continue;
                }
                d[el] = d[tmp] + 1;
                q.emplace(el);
            }
        }
        return d;
    }
    int dist(const int u, const int v){ return all_dist(u)[v]; }
    std::vector<int> t_sort() {
        const int n = this -> size();
		std::vector<int> deg(n);
		for(int i = 0; i < n; ++i) {
			for(const auto ed: (*this)[i]) {
				deg[ed]++;
			}
		}
		std::stack<int> sk;
		for(int i = 0; i < n; ++i) {
			if(deg[i] == 0) {
				sk.emplace(i);
			}
		}
		std::vector<int> ord;
		while(sk.size()) {
			const auto tmp = sk.top();
            sk.pop();
			ord.emplace_back(tmp);
			for(const auto ed: (*this)[tmp]) {
				if(--deg[ed] == 0) {
					sk.emplace(ed);
				}
			}
		}
		return ord.size() == size() ? ord : std::vector<int>{};
	}
    std::vector<edge> cycle() {
        const int n = size();
        std::vector<int> used(n);
        std::vector<edge> pre(n), cycle;
        const auto dfs = [&](const auto &f, const int i) -> bool {
            used[i] = 1;
			for(const auto &e: (*this)[i]) {
				if(used[e] == 0) {
					pre[e] = e;
					if(f(f, e)) {
						return true;
					}
				} else if(used[e] == 1) {
					int now = i;
					while(now != e) {
						cycle.emplace_back(pre[now]);
						now = pre[now].src;
					}
					cycle.emplace_back(e);
					return true;
				}
			}
			used[i] = 2;
			return false;
        };
        for(int i = 0; i < n; ++i) {
			if(used[i] == 0 && dfs(dfs, i)) {
				std::reverse(cycle.begin(), cycle.end());
				return cycle;
			}
		}
		return {};
    }
};
typedef std::vector<edge> ve;
typedef std::vector<ve> we;

/**
 * @brief グラフライブラリ
 */
#line 2 "C++/graph/ShortestPath.hpp"

#pragma GCC diagnostic ignored "-Wreorder"

#line 7 "C++/graph/ShortestPath.hpp"
struct ShortestPath {
private:
    const std::vector<long long> cost;
    const std::vector<int> src;
public:
    ShortestPath(const std::vector<long long> &cost, const std::vector<int> &src): cost(cost), src(src){}
    bool is_thru(const int i){ return src[i] != -1; }
    std::vector<int> path(int i) {
        std::vector<int> res;
        for(; i != -1; i = src[i]) {
            res.emplace_back(i);
        }
        std::ranges::reverse(res);
        return res;
    }
    std::vector<long long> get() const { return cost; }
};

/**
 * @brief 最短路
 */
#line 5 "C++/graph/WeightedGraph.hpp"
template <bool undirected = true> struct w_graph: graph<undirected> {
protected:
    using graph<undirected>::indexed;
    using graph<undirected>::id;
    using graph<undirected>::edges;
public:
    w_graph(const int n, const int indexed_ = 1): graph<undirected>(n, indexed_){}
    using graph<undirected>::get_edge;
    using graph<undirected>::all_dist;
    using graph<undirected>::dist;
    using graph<undirected>::t_sort;
    using graph<undirected>::cycle;
    void add(int a, int b, const long long cost) {
        a -= indexed, b -= indexed;
        (*this)[a].emplace_back(a, b, id, cost);
        edges.emplace_back(a, b, id++, cost);
        if(undirected) {
            (*this)[b].emplace_back(b, a, --id, cost);
            edges.emplace_back(b, a, id++, cost);
        }
    }
    void input(const int m) {
        for(int i = 0; i < m; ++i) {
            int a, b;
            long long c;
            std::cin >> a >> b >> c;
            add(a, b, c);
        }
    }
    ShortestPath dijkstra(const int v) {
        std::vector<long long> cst(this -> size(), (1LL << 61) - 1);
        std::vector<int> src(this -> size(), -1);
        std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> dj;
        cst[v] = 0;
        dj.emplace(cst[v], v);
        while(dj.size()) {
            const auto tmp = dj.top();
            dj.pop();
            if(cst[tmp.second] < tmp.first) {
                continue;
            }
            for(const auto &el: (*this)[tmp.second]) {
                if(chmin(cst[el], tmp.first + el.cost)) {
                    src[el] = tmp.second;
                    dj.emplace(cst[el], el);
                }
            }
        }
        return {cst, src};
    }
    std::vector<long long> spfa(const int v) {
        const int n = this -> size();
        std::vector<long long> cst(n, (1LL << 61) - 1);
        std::vector<int> pending(n), times(n);
        std::queue<int> q;
        q.emplace(v);
        pending[v] = 1;
        ++times[v];
        cst[v] = 0;
        while(!q.empty()) {
            const int p = q.front();
            q.pop();
            pending[p] = 0;
            for(const auto &e : (*this)[p]) {
                const long long next = cst[p] + e.cost;
                if(next >= cst[e]) {
                    continue;
                }
                cst[e] = next;
                if(!pending[e]) {
                    if(++times[e] >= n) {
                        cst.clear();
                        return cst;
                    }
                    pending[e] = 1;
                    q.emplace(e);
                }
            }
        }
		return cst;
    }
    std::vector<std::vector<long long>> warshall_floyd() {
		const int n = this -> size();
        const long long lim = (1LL << 61) - 1;
		std::vector cst(n, std::vector(n, lim));
		for(int i = 0; i < n; ++i) {
            cst[i][i] = 0;
        }
		for(int i = 0; i < n; ++i) {
            for(const auto &j: (*this)[i]) {
                cst[i][j] = j.cost;
            }
        }
		for(int k = 0; k < n; ++k) {
            for(int i = 0; i < n; ++i) {
                for(int j = 0; j < n; ++j) {
                    if(cst[i][k] == lim || cst[k][j] == lim) {
                        continue;
                    }
                    chmin(cst[i][j], cst[i][k] + cst[k][j]);
                }
            }
        }
		return cst;
	}
};

/**
 * @brief 重み付きグラフライブラリ
 */
#line 4 "test/shortestpath.test.cpp"
int main() {
    int n, m, s, t;
    std::cin >> n >> m >> s >> t;
    w_graph<false> g(n, 0);
    g.input(m);
    auto dj = g.dijkstra(s);
    if(!dj.is_thru(t)) {
        std::cout << "-1\n";
        return 0;
    }
    const auto ed = dj.path(t);
    std::cout << dj.get()[t] << ' ';
    const int len = ed.size() - 1;
    std::cout << len << '\n';
    for(int i = 0; i < len; ++i) {
        std::cout << ed[i] << ' ' << ed[i + 1] << '\n';
    }
}
Back to top page