結果

問題 No.859 路線A、路線B、路線C
ユーザー le_panda_noirle_panda_noir
提出日時 2020-07-09 00:06:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 1,000 ms
コード長 2,036 bytes
コンパイル時間 1,509 ms
コンパイル使用メモリ 99,672 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-15 10:46:21
合計ジャッジ時間 2,125 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 3 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <map>

using namespace std;
using ll = long long;
using vi = vector<int>;

void ins() {}
template<class T,class... Rest>void ins(T& v,Rest&... rest){cin>>v;ins(rest...);}

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
struct Graph {
  vector<map<int, long long>> edge;
  Graph(int n = 0) { resize(n); }
  void resize(int n) { edge.resize(n, map<int, long long>()); }
  void addEdge(int from, int to, long long weight) {
    edge[from][to] = weight; edge[to][from] = weight;
  }
  map<int, long long>& operator[](int from) { return edge[from]; }
};

template<class T>using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
int main() {
  ll XYZ[3];
  cin >> XYZ[0] >> XYZ[1] >> XYZ[2];
  char s0, s1;
  ll t0, t1;
  cin >> s0 >> t0 >> s1 >> t1;

  if (s0 > s1) {
    swap(s0, s1); swap(t0, t1);
  }
  if (s0 == s1 && t0 > t1)
    swap(t0, t1);

  Graph G(8); // A1, Ax, B1, By, C1, Cz, start, goal の8つ
  G.addEdge(0, 2, 1); G.addEdge(0, 4, 1); G.addEdge(2, 4, 1);
  G.addEdge(1, 3, 1); G.addEdge(1, 5, 1); G.addEdge(3, 5, 1);
  if (s0 == s1) {
    int a = s0-'A',
        b = (s0-'A'+1)%3,
        c = (s0-'A'+2)%3;
    G.addEdge(2*b, 2*b+1, XYZ[b]-1);
    G.addEdge(2*c, 2*c+1, XYZ[c]-1);
    G.addEdge(2*a, 6, t0-1);
    G.addEdge(6, 7, t1-t0);
    G.addEdge(7, 2*a+1, XYZ[a]-t1);
  } else {
    int b = s0-'A',
        c = s1-'A';
    int a = 6 / (b+1) / (c+1) - 1;
    G.addEdge(2*a, 2*a+1, XYZ[a]-1);
    G.addEdge(2*b, 6, t0-1); G.addEdge(6, 2*b+1, XYZ[b]-t0);
    G.addEdge(2*c, 7, t1-1); G.addEdge(7, 2*c+1, XYZ[c]-t1);
  }

  priority_queue_rev<pair<ll, int>> q;
  q.emplace(0, 6);
  vector<ll> distance(8, 1e18);
  distance[6] = 0;
  while (!q.empty()) {
    auto [c, from] = q.top(); q.pop();
    if (distance[from] < c)
      continue;
    for (const auto& [to, cost]:G[from]) {
      if (distance[to] > cost + distance[from])
        q.emplace(distance[to] = cost + distance[from], to);
    }
  }
  cout << distance[7] << endl;

  return 0;
}
0