test/graph/Dijkstra-restore.test.cpp

• View this file on GitHub
• Last update: 2023-05-30 04:49:31+09:00
• Problem: https://judge.yosupo.jp/problem/shortest_path

Depends on

• Dijkstra - 多次元ダイクストラ (lib/40-graph/Dijkstra.cpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path"
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
#include "../../lib/40-graph/Dijkstra.cpp"

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
	int N,M,s,t;
	cin >> N >> M >> s >> t;
	long long inf = 1e15;
	Dijkstra<long long> dijk(N,inf);
	while(M--) {
		int u,v,w; cin >> u >> v >> w;
		dijk.make_edge(u,v,w);
	}
	dijk.solve(s);
	long long cost = dijk.get(t);
	if(cost == inf) {
		cout << -1 << endl;
		return 0;
	}
	auto v = dijk.restore(t);
	cout << cost << " " << (int)v.size()-1 << endl;
	for(int i = 0; i+1 < v.size(); ++i) {
		cout << v[i] << " " << v[i+1] << endl;
	}
    return 0;
}

#line 1 "test/graph/Dijkstra-restore.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/shortest_path"
#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
#line 1 "lib/40-graph/Dijkstra.cpp"
/*
 * @title Dijkstra - 多次元ダイクストラ
 * @docs md/graph/Dijkstra.md
 */
template<class T> class Dijkstra {
    vector<long long> num_list;
    vector<long long> sum;
    int N;
    T inf;
    vector<vector<pair<T,int>>> edge;
    vector<T> cost;
    vector<int> dp;
    void resize(const int N) {
        edge.resize(N);
        cost.resize(N);
        dp.resize(N);
    }
public:
    Dijkstra(int N,T inf):inf(inf),num_list(1,N),sum(1,1),N(N){
        resize(N);
    }
    Dijkstra(initializer_list<long long> size_list,T inf):num_list(size_list),inf(inf),N(1){
        for(long long& e:num_list) N *= e;
        sum.resize(num_list.size(),1);
        for(int i = 0; i < num_list.size(); ++i) {
            for(int j = i + 1; j < num_list.size(); ++j) {
                sum[i] *= num_list[j];
            }
        }
        resize(N);
    }
    void make_edge(int from, int to, T w) {
        if(from < 0 || N <= from || to < 0 || N <= to) return;
        edge[from].push_back({ w,to });
    }
    void make_edge(initializer_list<long long> from_list, initializer_list<long long> to_list, T w) {
        int from = 0, to = 0;
        auto from_itr = from_list.begin(),to_itr = to_list.begin();
        for(int i = 0; i < num_list.size(); ++i) {
            if(*from_itr < 0 || num_list[i] <= *from_itr || *to_itr < 0 || num_list[i] <= *to_itr) return;
            from += (*from_itr)*sum[i];
            to   += (*to_itr)*sum[i];
            from_itr++;
            to_itr++;
        }
        edge[from].push_back({ w,to });
    }
    void solve(initializer_list<long long> start_list) {
        int start = 0;
        auto start_itr = start_list.begin();
        for(int i = 0; i < num_list.size(); ++i) {
            start += (*start_itr)*sum[i];
            start_itr++;
        }
        solve(start);
    }
    void solve(int start) {
        for(int i = 0; i < N; ++i) cost[i] = inf, dp[i] = -1;
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
        cost[start] = 0;
        pq.push({ 0,start });
        while (!pq.empty()) {
            auto [v,from] = pq.top();
            pq.pop();
            if(cost[from] < v) continue;
            for (auto [u,to] : edge[from]) {
                T w = v + u;
                if (w < cost[to]) {
                    cost[to] = w;
                    dp[to] = from;
                    pq.push({ w,to });
                }
            }
        }
        return;
    }
    T get(int idx){
        return cost[idx];
    }
    T get(initializer_list<long long> idx_list){
        int idx = 0;
        auto idx_itr = idx_list.begin();
        for(int i = 0; i < num_list.size(); ++i) {
            idx += (*idx_itr)*sum[i];
            idx_itr++;
        }
        return get(idx);
    }
    //vertex [start->node1->node2->...->idx]
    vector<int> restore(int idx) {
        vector<int> res = {idx};
        while(dp[idx] != -1) {
            idx = dp[idx];
            res.push_back(idx);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};
#line 9 "test/graph/Dijkstra-restore.test.cpp"

int main() {
    cin.tie(0);ios::sync_with_stdio(false);
	int N,M,s,t;
	cin >> N >> M >> s >> t;
	long long inf = 1e15;
	Dijkstra<long long> dijk(N,inf);
	while(M--) {
		int u,v,w; cin >> u >> v >> w;
		dijk.make_edge(u,v,w);
	}
	dijk.solve(s);
	long long cost = dijk.get(t);
	if(cost == inf) {
		cout << -1 << endl;
		return 0;
	}
	auto v = dijk.restore(t);
	cout << cost << " " << (int)v.size()-1 << endl;
	for(int i = 0; i+1 < v.size(); ++i) {
		cout << v[i] << " " << v[i+1] << endl;
	}
    return 0;
}

Back to top page