結果
問題 | No.807 umg tours |
ユーザー |
|
提出日時 | 2023-06-16 20:51:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,400 bytes |
コンパイル時間 | 1,812 ms |
コンパイル使用メモリ | 181,048 KB |
実行使用メモリ | 62,780 KB |
最終ジャッジ日時 | 2024-06-24 12:27:08 |
合計ジャッジ時間 | 12,672 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 WA * 2 |
ソースコード
#include <bits/stdc++.h>#define INF 10e9#define rep(i, a) for (int i = 0; i < (a); i++)using namespace std;typedef struct edge{int to;int cost;} edge;int main(){long long int n, m;cin >> n >> m;vector<edge> graph[n];long long int u, v, c;long long int i, j;for (i = 0; i < m; i++){cin >> u >> v >> c;edge e;e.to = v - 1;e.cost = c;graph[u - 1].push_back(e);e.to = u - 1;graph[v - 1].push_back(e);}long long int d[2][n];for (i = 0; i < n; i++){if (i == 0){d[0][i] = 0;d[1][i] = 0;}else{d[0][i] = INF;d[1][i] = INF;}}priority_queue<pair<pair<long long int, long long int>, long long int>, vector<pair<pair<long long int, long long int>, long long int>>, greater<pair<pair<long long int, long long int>, long long int>>> q;q.push(make_pair(make_pair(0, 0), 0));while (!q.empty()){pair<pair<long long int, long long int>, long long int> p = q.top();q.pop();long long int v = p.first.first;if ((p.second == 0) && (d[0][v] >= p.first.second)){for (i = 0; i < graph[v].size(); i++){edge e = graph[v][i];if (p.second == 0){if (d[0][e.to] > d[0][v] + e.cost){d[0][e.to] = d[0][v] + e.cost;q.push(make_pair(make_pair(e.to, d[0][e.to]), 0));}if (d[1][e.to] > d[0][v]){d[1][e.to] = d[0][v];q.push(make_pair(make_pair(e.to, d[1][e.to]), 1));}}}}else if ((p.second == 1) && (d[1][v] >= p.first.second)){for (i = 0; i < graph[v].size(); i++){edge e = graph[v][i];if (d[1][e.to] > d[1][v] + e.cost){d[1][e.to] = d[1][v] + e.cost;q.push(make_pair(make_pair(e.to, d[1][e.to]), 1));}}}}for (i = 0; i < n; i++){cout << (d[0][i] + d[1][i]) << endl;}}