結果
問題 | No.807 umg tours |
ユーザー |
![]() |
提出日時 | 2019-03-22 21:39:59 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 480 ms / 4,000 ms |
コード長 | 1,736 bytes |
コンパイル時間 | 1,391 ms |
コンパイル使用メモリ | 100,844 KB |
実行使用メモリ | 24,484 KB |
最終ジャッジ日時 | 2024-11-23 18:53:13 |
合計ジャッジ時間 | 7,529 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <iostream> #include <vector> #include <string> #include <cmath> #include <algorithm> #include <utility> #include <queue> #include <set> #include <map> #include <deque> #include <iomanip> #include <cstdio> #include <stack> #include <numeric> using namespace std; typedef long long ll; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<VI> VVI; #define MP make_pair #define PB push_back #define inf 1000000007 #define rep(i,n) for(int i=0;i<(int)(n);++i) vector<vector<pair<int,ll> > > g; int main(){ int n,m; cin >> n >> m; g.resize(n); rep(i,m){ int a,b; ll c; cin >> a >> b >> c; a--;b--; g[a].PB(MP(b,c)); g[b].PB(MP(a,c)); } vector<vector<ll> >dst(2,vector<ll>(n,1LL<<60)); priority_queue<pair<ll,pair<int,int> >,vector<pair<ll,pair<int,int> > > ,greater<pair<ll,pair<int,int> > > > pq; dst[0][0] = 0; dst[1][0] = 0; pq.push(MP(0,MP(0,0))); while(!pq.empty()){ auto x = pq.top(); pq.pop(); ll d = x.first; int now = x.second.first; int used = x.second.second; if(dst[used][now]!=d)continue; for(auto ed: g[now]){ int next = ed.first; ll p = ed.second; if(dst[used][next] > d+p){ dst[used][next] = d+p; pq.push(MP(d+p,MP(next,used))); } if(used==0){ if(dst[used+1][next] > d){ dst[used+1][next] = d; pq.push(MP(d,MP(next,used+1))); } } } } cout << 0 << endl; for(int i=1;i<n;i++){ cout << dst[0][i] + dst[1][i] << endl; } return 0; }