結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2024-09-18 19:07:43 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 431 ms / 4,000 ms |
コード長 | 1,264 bytes |
コンパイル時間 | 2,575 ms |
コンパイル使用メモリ | 221,004 KB |
実行使用メモリ | 36,008 KB |
最終ジャッジ日時 | 2024-09-18 19:07:53 |
合計ジャッジ時間 | 8,186 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;int main() {cin.tie(nullptr);ios::sync_with_stdio(false);ll N,M;cin>>N>>M;vector<vector<pair<ll,ll>>> G(N);for(int i=0;i<M;i++){ll a,b,c;cin>>a>>b>>c;a--;b--;G[a].push_back({b,c});G[b].push_back({a,c});}vector<vector<ll>> D(N,vector<ll>(2,1e18));D[0][0]=0;priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,greater<pair<ll,pair<ll,ll>>>> Q;Q.push({0,{0,0}});vector<vector<bool>> seen(N,vector<bool>(2,0));while(!Q.empty()){ll c=Q.top().first;auto [n,d]=Q.top().second;Q.pop();if(seen[n][d])continue;seen[n][d]=1;for(auto [v,w]:G[n]){if(seen[v][d])continue;if(D[v][d]>c+w){D[v][d]=c+w;Q.push({c+w,{v,d}});}}if(d==0){for(auto [v,w]:G[n]){if(seen[v][1])continue;if(D[v][1]>c){D[v][1]=c;Q.push({c,{v,1}});}}}}for(int i=0;i<N;i++){cout<<min(D[i][0]*2,D[i][0]+D[i][1])<<endl;}}