結果
問題 |
No.807 umg tours
|
ユーザー |
![]() |
提出日時 | 2020-09-28 22:53:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,174 bytes |
コンパイル時間 | 1,812 ms |
コンパイル使用メモリ | 179,596 KB |
実行使用メモリ | 22,552 KB |
最終ジャッジ日時 | 2024-07-02 18:13:06 |
合計ジャッジ時間 | 11,475 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 TLE * 1 -- * 1 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define INF 1000000000000000000 using ll=long long; using Graph=vector<vector<pair<int,ll>>>; int main(){ int N,M; cin>>N>>M; Graph G(N); for(int i=0;i<M;i++){ int a,b; ll c; cin>>a>>b>>c; a--; b--; G[a].push_back(make_pair(b,c)); G[b].push_back(make_pair(a,c)); } vector<ll> dist1(N,INF); dist1[0]=0; priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq1,pq2; pq1.push(make_pair(dist1[0],0)); while(!pq1.empty()){ int v=pq1.top().second; pq1.pop(); for(auto p:G[v]){ int nv=p.first; ll d=p.second; if(dist1[v]+d<dist1[nv]){ dist1[nv]=dist1[v]+d; pq1.push(make_pair(dist1[nv],nv)); } } } vector<ll> dist2=dist1; pq2.push(make_pair(dist2[0],0)); while(!pq2.empty()){ int v=pq2.top().second; pq2.pop(); for(auto p:G[v]){ int nv=p.first; ll d=p.second; if(dist2[nv]>min(dist1[v],dist2[v]+d)){ dist2[nv]=min(dist1[v],dist2[v]+d); pq2.push(make_pair(dist2[nv],nv)); } } } for(int i=0;i<N;i++){ cout<<dist1[i]+dist2[i]<<'\n'; } }