結果
問題 | No.859 路線A、路線B、路線C |
ユーザー |
![]() |
提出日時 | 2019-08-09 21:46:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,632 bytes |
コンパイル時間 | 1,751 ms |
コンパイル使用メモリ | 183,236 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-19 11:35:31 |
合計ジャッジ時間 | 2,195 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#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'; }