結果

問題 No.3393 Move on Highway
コンテスト
ユーザー yu23578
提出日時 2025-11-21 19:08:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 608 ms / 3,000 ms
コード長 2,413 bytes
コンパイル時間 2,469 ms
コンパイル使用メモリ 213,772 KB
実行使用メモリ 30,360 KB
最終ジャッジ日時 2025-11-28 20:58:55
合計ジャッジ時間 17,412 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define int long long

int INF = 1e18;

signed main(){
	//ステップ1. 入力の受取り
	int N,M,C;
	cin>>N>>M>>C;
	vector<vector<pair<int,int>>> G(N);
	for(int i = 0; i < M; i++){
		int u,v,w; cin>>u>>v>>w;
		u--; v--;
		w += C; //利用料金の加算
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	
	//ステップ2. 頂点1から頂点iまでの最短距離を求める
	vector<int> Dist_1_to_i(N,INF);
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> Q; //(距離,現在の街)
	Q.push({0,0});
	Dist_1_to_i[0] = 0;
	while(!Q.empty()){
		int now_dist = Q.top().first;
		int now_pos = Q.top().second;
		Q.pop();
		if(Dist_1_to_i[now_pos] != now_dist) continue;
		for(int i = 0; i < G[now_pos].size(); i++){
			int nex_pos = G[now_pos][i].first;
			int nex_dist = G[now_pos][i].second;
			if(Dist_1_to_i[nex_pos] > now_dist + nex_dist){
				Dist_1_to_i[nex_pos] = now_dist + nex_dist;
				Q.push({Dist_1_to_i[nex_pos],nex_pos});
			}
		}
	}
	
	//ステップ3. 頂点(状態3,N) から頂点(状態2,i) までの最短距離を求める.
	vector<vector<int>> Dist_N_to_i(4,vector<int>(N,INF));
	priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> R; //(距離,現在の状態,現在の街)
	R.push({0,3,N-1});
	Dist_N_to_i[3][N-1] = 0;
	while(!R.empty()){
	  	int now_dist = get<0>(R.top());
	  	int now_state = get<1>(R.top());
	  	int now_pos = get<2>(R.top());
	  	R.pop();
	  	for(int i = 0; i < G[now_pos].size(); i++){
	  		int nex_pos = G[now_pos][i].first;
	  		int nex_dist = G[now_pos][i].second;
	  		//状態はそのままの遷移
	  		if(Dist_N_to_i[now_state][nex_pos] > Dist_N_to_i[now_state][now_pos] + nex_dist){
	  			Dist_N_to_i[now_state][nex_pos] = Dist_N_to_i[now_state][now_pos] + nex_dist;
	  			R.push({Dist_N_to_i[now_state][nex_pos],now_state,nex_pos});
	  		}
	  		//状態3から状態2へ遷移(ガソリン代無料)
	  		if(now_state == 3){
	  			if(Dist_N_to_i[2][nex_pos] > Dist_N_to_i[now_state][now_pos] + C){
	  				Dist_N_to_i[2][nex_pos] = Dist_N_to_i[now_state][now_pos] + C;
	  				R.push({Dist_N_to_i[2][nex_pos],2,nex_pos});
	  			}
	  		}
	  	}
	}
	
	//ステップ4. 解答の出力
	vector<int> Answer(N);
	for(int i = 1; i < N; i++){
		Answer[i] = min(Dist_1_to_i[i] + Dist_N_to_i[2][i], Dist_1_to_i[N-1]);
		cout << Answer[i] << "\n";
	}
}
0