結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー manjuuu_onsen
提出日時 2021-09-06 20:28:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 18 ms / 5,000 ms
コード長 2,820 bytes
コンパイル時間 2,603 ms
コンパイル使用メモリ 194,664 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-22 20:16:36
合計ジャッジ時間 4,096 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In constructor 'ShortestPathDAG<T>::ShortestPathDAG(std::vector<std::vector<std::pair<int, T> > >, int, T)':
main.cpp:41:34: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   41 |                         for(auto [j, cost] : Graph[i]) {
      |                                  ^
main.cpp: In function 'int main()':
main.cpp:112:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  112 |                 for(auto [j, c] : SPD.dag()[i])v[i].push_back(j);
      |                          ^

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pint = pair<int,int>;

template<class T> class ShortestPathDAG { private:
	using P = pair<int,T>;
	vector<vector<P>> DAG, Graph;
	vector<T> dist;
	T INF;
	int N, start;
 
	vector<T> dijkstra(){
		vector<T> dist(N, INF);
		dist[start] = 0;
		priority_queue<pair<T,int>, vector<pair<T,int>>, greater<pair<T,int>>> que;
		que.push({0, start});
		while(que.size()) {
			int ver = que.top().second;
			T cost = que.top().first; que.pop();
			if(cost != dist[ver])continue;
			for(auto i : Graph[ver]) {
				if(dist[i.first] > cost + i.second) {
					dist[i.first] = cost + i.second;
					que.push({dist[i.first], i.first});
				}
			}
		}
		return dist;
	}

public:
	ShortestPathDAG(){}
	ShortestPathDAG(vector<vector<P>> _Graph, int _start = 0, T _INF = numeric_limits<T>::max()): N(_Graph.size()), start(_start) {
		INF = _INF;
		Graph = _Graph;
		dist = dijkstra();
		DAG = vector<vector<P>>(N);
		for(int i = 0; i < N; i++) {
			for(auto [j, cost] : Graph[i]) {
				if(dist[j] - dist[i] == cost) {
					DAG[i].push_back({j, cost});
				}
			}
		}
		
	}
	vector<T>& dis() {return dist;}
	vector<vector<P>>& dag() {return DAG;}
};

class EraseVertex { private:

	vector<vector<int>> Graph, ReversedGraph, ErasedGraph;
	vector<int> ok;
	int N;

	void dfs0(ll v) {
		if(ok[v] & 1)return;
		ok[v]++;
		for(auto i : Graph[v]) {
			dfs0(i);
		}
	}
	void dfs1(ll v) {
		if(ok[v] & 2)return;
		ok[v] += 2;
		for(auto i : ReversedGraph[v]) {
			dfs1(i);
		}
	}

public:

	EraseVertex(const vector<vector<int>>& edge, int s, int t) { 
		N = edge.size(); Graph = edge; ok = vector<int>(N);
		ReversedGraph = ErasedGraph = vector<vector<int>>(N);
		for(int i = 0; i < N; i++) {
			for(auto j : Graph[i]) ReversedGraph[j].push_back(i); 
		}
		dfs0(s), dfs1(t);
		for(int i = 0; i < N; i++) {
			for(auto j : Graph[i]) {
				if(ok[i] == 3 && ok[j] == 3) {
					ErasedGraph[i].push_back(j);
				}
			}
		}
	}
	auto& rg() {return ReversedGraph;}
	auto& eg() {return ErasedGraph;}

};

template<class T> ostream& operator<<(ostream& os, const vector<T> arr){ for(int i = 0; i < (int)arr.size(); i++)cout << arr[i] << (i == (int)arr.size() -1 ? "" : " "); return os;}

int main()
{
	int N, M, S, G;
	cin >> N >> M >> S >> G;
	vector<vector<pair<int,int>>> edges(N);
	for(int i = 0; i < M; i++) {
		int a, b, c; cin >> a >> b >> c;
		edges[a].push_back({b, c});
		edges[b].push_back({a, c});
	}

	ShortestPathDAG<int> SPD(edges, S, 1e9);
	vector<vector<int>> v(N);
	for(int i = 0; i < N; i++) {
		for(auto [j, c] : SPD.dag()[i])v[i].push_back(j);
	}
	EraseVertex EV(v, S, G);

	auto dag = EV.eg();

	vector<int> ans = {S};
	while(ans.back() != G) {
		int p = ans.back();
		sort(dag[p].begin(), dag[p].end());
		ans.push_back(dag[p][0]);
	}
	
	cout << ans << endl;


}
0