結果
問題 | No.807 umg tours |
ユーザー |
![]() |
提出日時 | 2019-03-22 21:45:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 531 ms / 4,000 ms |
コード長 | 1,683 bytes |
コンパイル時間 | 1,806 ms |
コンパイル使用メモリ | 179,112 KB |
実行使用メモリ | 24,592 KB |
最終ジャッジ日時 | 2024-11-23 18:53:43 |
合計ジャッジ時間 | 8,520 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; typedef pair<ll ,P> P3; typedef pair<P ,P> PP; const ll MOD = ll(1e9+7); const int IINF = INT_MAX; const ll LLINF = LLONG_MAX; const int MAX_N = int(1e5 + 5); const double EPS = 1e-6; const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0}; #define REP(i, n) for (int i = 0; i < n; i++) #define REPR(i, n) for (int i = n; i >= 0; i--) #define SORT(v) sort((v).begin(), (v).end()) #define SORTR(v) sort((v).rbegin(), (v).rend()) #define ALL(v) (v).begin(), (v).end() ll n, m; ll dmin[2][MAX_N]; vector<vector<P> > g; void dijkstra(){ REP(i,2)fill(dmin[i],dmin[i]+n,LLINF/3); dmin[0][0] = 0; dmin[1][0] = 0; priority_queue<P3, vector<P3>, greater<P3> > que; que.push({0,{0,0}}); while(!que.empty()){ P3 p = que.top(); que.pop(); ll f = p.second.first, u = p.second.second; if(dmin[f][u] < p.first)continue; for(auto e : g[u]){ ll v = e.first, cost = e.second; if(dmin[f][v] > dmin[f][u] + cost){ dmin[f][v] = dmin[f][u] + cost; que.push({dmin[f][v], {f, v}}); } if(f==0 && dmin[1][v] > dmin[0][u]){ dmin[1][v] = dmin[0][u]; que.push({dmin[1][v], {1, v}}); } } } } int main() { cin >> n >> m; g.resize(n); REP(i,m){ ll a, b, c; cin >> a >> b >> c; a--; b--; g[a].push_back({b,c}); g[b].push_back({a,c}); } dijkstra(); REP(i,n){ cout << dmin[0][i] + dmin[1][i] << endl; } return 0; }