結果
問題 |
No.160 最短経路のうち辞書順最小
|
ユーザー |
|
提出日時 | 2022-08-17 23:20:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 15 ms / 5,000 ms |
コード長 | 1,176 bytes |
コンパイル時間 | 4,339 ms |
コンパイル使用メモリ | 256,384 KB |
最終ジャッジ日時 | 2025-01-30 23:35:52 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; using ll = long long; int n,m,s,g; using P = pair<int,int>; vector<vector<P>> G; void solve(){ vector<vector<int>> dist(n,vector<int>(n,INT_MAX/2)); for(int i =0;i<n;i++)dist[i][i] = 0; for(int i = 0;i<n;i++){ for(auto &[to,cost]:G[i]){ dist[i][to] = cost; dist[to][i] = cost; } } for(int k = 0;k<n;k++){ for(int i = 0;i<n;i++){ for(int j = 0;j<n;j++){ dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]); } } } int sumcost = dist[s][g]; cout<<s<<' '; int cur = s; auto dist2 = vector<vector<int>>(n,vector<int>(n,INT_MAX/2)); for(int i = 0;i<n;i++){ for(auto &[to,cost]:G[i]){ dist2[i][to] = cost; dist2[to][i] = cost; } } while(cur!=g){ for(int i = 0;i<n;i++){ if(dist2[cur][i]+dist[i][g]==sumcost){ sumcost -= dist2[cur][i]; cout<<i<<' '; cur = i; break; } } } //cout<<g; cout<<endl; } signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> m >> s >> g; G = vector<vector<P>>(n); for(int i = 0;i<m;i++){ int a,b,c; cin >> a >> b >> c; G[a].push_back(P(b,c)); } solve(); }