結果
問題 | No.807 umg tours |
ユーザー |
![]() |
提出日時 | 2019-03-22 21:47:49 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 489 ms / 4,000 ms |
コード長 | 1,833 bytes |
コンパイル時間 | 895 ms |
コンパイル使用メモリ | 104,660 KB |
実行使用メモリ | 21,212 KB |
最終ジャッジ日時 | 2024-11-23 18:55:03 |
合計ジャッジ時間 | 7,439 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <cstdio>#include <cstring>#include <iostream>#include <string>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>#include <cassert>#include <fstream>#define popcount __builtin_popcountusing namespace std;typedef long long int ll;typedef pair<ll, int> P;int n, m;vector<P> g[100001];const ll INF=1e16;int main(){cin>>n>>m;for(int i=0; i<m; i++){int a, b; ll c;cin>>a>>b>>c; a--; b--;g[a].push_back(P(c, b));g[b].push_back(P(c, a));}ll d[2][100001];fill(d[0], d[0]+n, INF);fill(d[1], d[1]+n, INF);d[0][0]=0, d[1][0]=0;priority_queue<P, vector<P>, greater<P>> que;que.push(P(0, 0));que.push(P(0, n));while(!que.empty()){P p=que.top(); que.pop();int x=p.second;if(x>=n){if(p.first>d[1][x-n]) continue;}else{if(p.first>d[0][x]) continue;}if(x>=n){for(auto q:g[x-n]){int y=q.second;if(d[1][y]>d[1][x-n]+q.first){d[1][y]=d[1][x-n]+q.first;que.push(P(d[1][y], y+n));}}}else{for(auto q:g[x]){int y=q.second;if(d[0][y]>d[0][x]+q.first){d[0][y]=d[0][x]+q.first;que.push(P(d[0][y], y));}if(d[1][y]>d[0][x]){d[1][y]=d[0][x];que.push(P(d[1][y], y+n));}}}}for(int i=0; i<n; i++){cout<<d[0][i]+d[1][i]<<endl;}return 0;}