結果
問題 | No.807 umg tours |
ユーザー |
![]() |
提出日時 | 2023-03-02 07:04:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 500 ms / 4,000 ms |
コード長 | 1,901 bytes |
コンパイル時間 | 4,548 ms |
コンパイル使用メモリ | 256,328 KB |
最終ジャッジ日時 | 2025-02-11 00:59:49 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;using ll=long long;using ld=long double;ld pie=3.14159265359;ll inf=10000000000000001;ll mod=1000000007;int main(){ll n,m;cin >> n >> m;vector<vector<pair<ll,ll>>>g(n);for (ll i = 0; i < m; i++){ll a,b,c;cin >> a >> b >> c;a--,b--;g[a].push_back({b,c});g[b].push_back({a,c});}vector<ll>memo(n,inf),memo2(n,inf);memo[0]=0;priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>que;que.push({0,0});vector<ll>ch(n,0);while (!que.empty()){ll v=que.top().second;que.pop();ch[v]=0;for (ll i = 0; i < g[v].size(); i++){if (memo[g[v][i].first]>memo[v]+g[v][i].second){memo[g[v][i].first]=memo[v]+g[v][i].second;if (ch[g[v][i].first]==0){que.push({memo[g[v][i].first],g[v][i].first});ch[g[v][i].first]=1;}}if (memo2[g[v][i].first]>memo[v]){memo2[g[v][i].first]=memo[v];if (ch[g[v][i].first]==0){que.push({memo2[g[v][i].first],g[v][i].first});ch[g[v][i].first]=1;}}if (memo2[g[v][i].first]>memo2[v]+g[v][i].second){memo2[g[v][i].first]=memo2[v]+g[v][i].second;if (ch[g[v][i].first]==0){que.push({memo2[g[v][i].first],g[v][i].first});ch[g[v][i].first]=1;}}}}ll ans=inf;cout << 0 << endl;for (ll i = 1; i < n; i++){cout << memo[i]+memo2[i] << endl;}}