結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
![]() |
提出日時 | 2015-08-25 01:14:57 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 13 ms / 5,000 ms |
コード長 | 816 bytes |
コンパイル時間 | 1,309 ms |
コンパイル使用メモリ | 168,468 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-18 13:15:44 |
合計ジャッジ時間 | 2,265 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int n,m,s,g; cin>>n>>m>>s>>g; vector<int> dp(n,(1<<25)); vector<vector<int>> dist(n,vector<int>(n,(1<<25))); while(m--){ int a,b,c; cin>>a>>b>>c; dist[a][b]=dist[b][a]=c; } dp[g]=0; priority_queue<pair<int,int>> pq; pq.push(make_pair(0,g)); while(!pq.empty()){ auto now=pq.top(); pq.pop(); int cost=-now.first,cur=now.second; if(cost>dp[cur]) continue; for(int i=0;i<n;i++){ if(dist[cur][i]!=(1<<25)){ if(cost+dist[cur][i]<dp[i]){ dp[i]=cost+dist[cur][i]; pq.push(make_pair(-dp[i],i)); } } } } int cur=s; cout<<s; while(cur!=g){ for(int i=0;i<n;i++){ if(dist[i][cur]!=(1<<25)){ if(dp[cur]==dp[i]+dist[i][cur]){ cout<<" "<<i; cur=i; break; } } } } cout<<endl; return 0; }