結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2019-08-28 21:47:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 286 ms / 4,000 ms |
コード長 | 1,686 bytes |
コンパイル時間 | 1,017 ms |
コンパイル使用メモリ | 108,532 KB |
実行使用メモリ | 42,284 KB |
最終ジャッジ日時 | 2024-11-24 09:13:13 |
合計ジャッジ時間 | 6,237 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <limits>#include <iostream>#include <algorithm>#include <iomanip>#include <map>#include <set>#include <queue>#include <stack>#include <numeric>#include <bitset>#include <cmath>static const int MOD = 1000000007;using ll = long long;using u32 = uint32_t;using namespace std;template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;template <typename T>struct edge {int from, to; T cost;edge(int to, T cost) : from(-1), to(to), cost(cost) {}edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}};template <typename T>vector<T> dijkstra(int s,vector<vector<edge<T>>> &G){size_t n=G.size();vector<T> d(n, INF<T>);priority_queue<pair<T, int>,vector<pair<T, int>>,greater<>> Q;d[s]=0;Q.emplace(0,s);while(!Q.empty()){T cost; int i;tie(cost, i) = Q.top(); Q.pop();if(d[i] < cost) continue;for (auto &&e : G[i]) {auto cost2 = cost + e.cost;if(d[e.to] <= cost2) continue;d[e.to] = cost2;Q.emplace(d[e.to], e.to);}}return d;}int main() {int n, m;cin >> n >> m;vector<vector<edge<ll>>> G(2*n);for (int i = 0; i < m; ++i) {int a, b; ll c; scanf("%d %d %lld", &a, &b, &c);a--; b--;G[a].emplace_back(b, c);G[b].emplace_back(a, c);G[a].emplace_back(b+n, 0);G[b].emplace_back(a+n, 0);G[a+n].emplace_back(b+n, c);G[b+n].emplace_back(a+n, c);}auto dist = dijkstra(0, G);puts("0");for (int i = 1; i < n; ++i) {printf("%lld\n", dist[i]+dist[i+n]);}return 0;}