結果
問題 | No.807 umg tours |
ユーザー |
![]() |
提出日時 | 2019-03-24 22:14:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,177 ms / 4,000 ms |
コード長 | 1,952 bytes |
コンパイル時間 | 1,421 ms |
コンパイル使用メモリ | 118,052 KB |
実行使用メモリ | 61,464 KB |
最終ジャッジ日時 | 2024-11-23 19:22:24 |
合計ジャッジ時間 | 22,851 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <cstdio>#include <cstdlib>#include <cmath>#include <climits>#include <cassert>#include <iostream>#include <iomanip>#include <string>#include <stack>#include <queue>#include <vector>#include <map>#include <set>#include <algorithm>#include <numeric>#include <bitset>#define all(c) c.begin(), c.end()#define rall(c) c.rbegin(), c.rend()#define debug(x) cerr << #x << ": " << x << endlusing namespace std;typedef long long ll;typedef pair<ll, ll> Pll;typedef pair<int, int> Pii;const ll MOD = 1000000007;const long double EPS = 1e-10;const int MAX_N = 112345;const int dyx[4][2] = {{ 0, 1}, {-1, 0}, {0,-1}, {1, 0}};int n,m,a,b; ll c;map<ll, ll> d;priority_queue< Pll, vector<Pll>, greater<Pll> > que;map<ll, vector<Pll> > edges;void dijkstra(ll start){d[start] = 0;d[n+start] = 0;que.push(Pll(0, start));while(!que.empty()){Pll v = que.top(); que.pop();if(d.find(v.second) != d.end() && d[v.second] < v.first) continue;for(Pll e: edges[v.second]){if(d.find(e.first) == d.end() || d[e.first] > d[v.second] + e.second){d[e.first] = d[v.second] + e.second;que.push(Pll(d[e.first], e.first));}}}}int main() {cin >> n >> m;for(int i=0;i<m;++i) {cin >> a >> b >> c;--a; --b;edges[a].emplace_back(b, c);edges[b].emplace_back(a, c);edges[a].emplace_back(n+b, 0);edges[b].emplace_back(n+a, 0);edges[n+a].emplace_back(n+b, c);edges[n+b].emplace_back(n+a, c);}dijkstra(0);for(int i=0;i<n;++i) {cout << d[i]+d[n+i] << endl;// cerr << i << ": " << d[0][i] << " " << d[1][i] << " " << longest_edge[i] << endl;}}/*間違えてしまう入力の例4 41 2 43 4 92 4 11 4 8ツアー 3 について,最短移動距離は 22 なのに 19 と答えてしまう*/