結果
問題 | No.859 路線A、路線B、路線C |
ユーザー |
|
提出日時 | 2021-02-08 20:36:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 1,877 bytes |
コンパイル時間 | 2,862 ms |
コンパイル使用メモリ | 231,676 KB |
最終ジャッジ日時 | 2025-01-18 16:28:04 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;const long long INF = 1LL<<60;void add(map<string, vector<tuple<string, long long> > > &edges, string x, string y, long long d) {edges[x].emplace_back(y, d);edges[y].emplace_back(x, d);}int main() {ios_base::sync_with_stdio(0);cin.tie(0);int x, y, z;cin >> x >> y >> z;map<string, vector<tuple<string, long long> > > edges;string a1 = "a1", an = "a" + to_string(x);string b1 = "b1", bn = "b" + to_string(y);string c1 = "c1", cn = "c" + to_string(z);add(edges, a1, an, x-1);add(edges, b1, bn, y-1);add(edges, c1, cn, z-1);add(edges, a1, b1, 1);add(edges, b1, c1, 1);add(edges, c1, a1, 1);add(edges, an, bn, 1);add(edges, bn, cn, 1);add(edges, cn, an, 1);vector<string> s(2);vector<int> t(2);for (int i = 0; i < 2; i++) {cin >> s[i] >> t[i];string v = to_string(i);if (s[i] == "A") {add(edges, v, a1, abs(1-t[i]));add(edges, v, an, abs(x-t[i]));} else if (s[i] == "B") {add(edges, v, b1, abs(1-t[i]));add(edges, v, bn, abs(y-t[i]));} else {add(edges, v, c1, abs(1-t[i]));add(edges, v, cn, abs(z-t[i]));}}if (s[0] == s[1])add(edges, "0", "1", abs(t[0] - t[1]));map<string, long long> dist {{a1, INF}, {b1, INF}, {c1, INF},{an, INF}, {bn, INF}, {cn, INF},{"0", 0}, {"1", INF}};priority_queue<pair<long long, string>, vector<pair<long long, string>>, greater<pair<long long, string>> > q;q.emplace(0, "0");while (!q.empty()) {string v;long long d;tie(d, v) = q.top();q.pop();if (d > dist[v])continue;for (auto &[w, cost]: edges[v]) {if (d + cost < dist[w]) {dist[w] = d + cost;q.emplace(dist[w], w);}}}cout << dist["1"] << endl;return 0;}