結果
問題 | No.859 路線A、路線B、路線C |
ユーザー | risujiroh |
提出日時 | 2019-08-09 21:46:58 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,632 bytes |
コンパイル時間 | 1,795 ms |
コンパイル使用メモリ | 179,920 KB |
実行使用メモリ | 4,384 KB |
最終ジャッジ日時 | 2023-09-26 17:38:22 |
合計ジャッジ時間 | 2,644 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 1 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 2 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,384 KB |
testcase_13 | AC | 1 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using lint = long long; template<class T = int> using V = vector<T>; template<class T = int> using VV = V< V<T> >; struct Edge { int to, cost; }; template<class T, class Edge> V<T> dijkstra(const VV<Edge>& g, int s = 0) { V<T> dist(g.size(), numeric_limits<T>::max()); using P = pair<T, int>; priority_queue< P, V<P>, greater<P> > pque; pque.emplace(dist[s] = 0, s); while (!pque.empty()) { T d; int v; tie(d, v) = pque.top(); pque.pop(); if (d > dist[v]) continue; for (const auto& e : g[v]) if (dist[v] + e.cost < dist[e.to]) { pque.emplace(dist[e.to] = dist[v] + e.cost, e.to); } } return dist; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int x, y, z; cin >> x >> y >> z; V<char> c(2); V<> v(2); for (int i = 0; i < 2; ++i) cin >> c[i] >> v[i]; VV<Edge> g(8); auto add_edge = [&](int u, int v, int c) -> void { g[u].emplace_back(Edge{v, c}); g[v].emplace_back(Edge{u, c}); }; add_edge(0, 1, x - 1); add_edge(2, 3, y - 1); add_edge(4, 5, z - 1); add_edge(0, 2, 1), add_edge(0, 4, 1), add_edge(2, 4, 1); add_edge(1, 3, 1), add_edge(1, 5, 1), add_edge(3, 5, 1); for (int i = 0; i < 2; ++i) { if (c[i] == 'A') { add_edge(0, 6 + i, v[i] - 1); add_edge(6 + i, 1, x - v[i]); } else if (c[i] == 'B') { add_edge(2, 6 + i, v[i] - 1); add_edge(6 + i, 3, y - v[i]); } else { add_edge(4, 6 + i, v[i] - 1); add_edge(6 + i, 5, z - v[i]); } } if (c[0] == c[1]) { add_edge(6, 7, abs(v[0] - v[1])); } cout << dijkstra<lint>(g, 6)[7] << '\n'; }