結果

問題 No.3393 Move on Highway
コンテスト
ユーザー Unbakedbread
提出日時 2026-03-15 23:59:55
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 501 ms / 3,000 ms
コード長 1,085 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,632 ms
コンパイル使用メモリ 345,692 KB
実行使用メモリ 38,468 KB
最終ジャッジ日時 2026-03-16 00:00:16
合計ジャッジ時間 19,242 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using ll = long long;

int main(void) {
	int N, M, C;
	cin >> N >> M >> C;
	
	vector<vector<pair<int, int>>> G(N * 2);
	while(M--) {
		int u, v, w;
		cin >> u >> v >> w, --u, --v;
		G[u].emplace_back(make_pair(v, C + w));
		G[v].emplace_back(make_pair(u, C + w));
		G[N + u].emplace_back(make_pair(N + v, C + w));
		G[N + v].emplace_back(make_pair(N + u, C + w));
		G[u].emplace_back(make_pair(N + v, C));
		G[v].emplace_back(make_pair(N + u, C));
	}
	
	auto dijkstra = [&](int st) {
		vector<ll> d(N * 2, 1e18);
		priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> que;
		d[st] = 0;
		que.push(make_pair(d[st], st));
		
		while(!que.empty()) {
			auto [vd, v] = que.top();
			que.pop();
			if(vd != d[v]) continue;
			
			for(auto [nv, c] : G[v]) {
				if(vd + c < d[nv]) {
					d[nv] = vd + c;
					que.push(make_pair(d[nv], nv));
				}
			}
		}
		
		return d;
	};
	
	vector<ll> ds = dijkstra(0), dt = dijkstra(N - 1);
	for(int i = 1; i < N; ++i) cout << min(ds[N - 1], ds[i] + dt[N + i]) << "\n";
	return 0;
}
0