結果
問題 | No.859 路線A、路線B、路線C |
ユーザー |
![]() |
提出日時 | 2020-02-06 13:37:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,038 bytes |
コンパイル時間 | 1,002 ms |
コンパイル使用メモリ | 98,724 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-25 06:47:16 |
合計ジャッジ時間 | 1,429 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 11 WA * 1 |
ソースコード
#include<algorithm>#include<cmath>#include<cstdio>#include<functional>#include<iomanip>#include<iostream>#include<map>#include<queue>#include<set>#include<string>#include<utility>#include<vector>using namespace std;typedef long long ll;const ll mod = 1000000007;#define rep(i,n) for(int i=0;i<n;i++)#define repl(i,s,e) for(int i=s;i<e;i++)#define reple(i,s,e) for(int i=s;i<=e;i++)#define revrep(i,n) for(int i=n-1;i>=0;i--)#define all(x) (x).begin(),(x).end()int nodeNumber(char s, ll t, ll x, ll y, ll z, int count){if (s == 'A' && t == 0) return 0;if (s == 'A' && t == x - 1) return 1;if (s == 'B' && t == 0) return 2;if (s == 'B' && t == y - 1) return 3;if (s == 'C' && t == 0) return 4;if (s == 'C' && t == z - 1) return 5;return count;}int main(){ll x, y, z;cin >> x >> y >> z;char s0, s1;ll t0, t1;cin >> s0 >> t0;cin >> s1 >> t1;--t0;--t1;//グラフの作成//路線をそのままグラフにするとノード数~10^9となってしまうため、重み付きグラフに圧縮する。//-A1-Ax-//|| | |//|B1-By|//|| | |//-C1-Cz-//ノード数int count = 6;//開始位置・終了位置判定int start = nodeNumber(s0, t0, x, y, z, count);if (start == count)count++;;int end = nodeNumber(s1, t1, x, y, z, count);if (end == count)count++;;//ノードの番号変換//A1・・・・・・0//AX・・・・・・1//B1・・・・・・2//By・・・・・・3//C1・・・・・・4//Cz・・・・・・5//Aダミー1・・・6//Aダミー2・・・7const ll MAX_WEIGHT = 10000000000;vector<vector<ll>> G(count, vector<ll>(count, MAX_WEIGHT));//初期化rep(i, count) G[i][i] = 0;G[0][1] = G[1][0] = x - 1;G[0][2] = G[2][0] = 1;G[0][4] = G[4][0] = 1;G[1][3] = G[3][1] = 1;G[1][5] = G[5][1] = 1;G[2][3] = G[3][2] = y - 1;G[2][4] = G[4][2] = 1;G[3][5] = G[5][3] = 1;G[4][5] = G[5][4] = z - 1;//開始・終了駅の初期化if (start >= 6){if (s0 == 'A'){//G[0][1] = G[1][0] = MAX_WEIGHT;G[0][start] = G[start][0] = t0;G[start][1] = G[1][start] = x - 1 - t0;}else if (s0 == 'B'){//G[2][3] = G[3][2] = MAX_WEIGHT;G[2][start] = G[start][2] = t0;G[start][3] = G[3][start] = y - 1 - t0;}else if (s0 == 'C'){//G[4][5] = G[5][4] = MAX_WEIGHT;G[4][start] = G[start][4] = t0;G[start][5] = G[5][start] = z - 1 - t0;}}if (end >= 6){if (s1 == 'A'){//G[0][1] = G[1][0] = MAX_WEIGHT;G[0][end] = G[end][0] = t1;G[end][1] = G[1][end] = x - 1 - t1;}else if (s1 == 'B'){//G[2][3] = G[3][2] = MAX_WEIGHT;G[2][end] = G[end][2] = t1;G[end][3] = G[3][end] = y - 1 - t1;}else if (s1 == 'C'){//G[4][5] = G[5][4] = MAX_WEIGHT;G[4][end] = G[end][4] = t1;G[end][5] = G[5][end] = z - 1 - t1;}}//ワーシャルフロイドrep(i, count)rep(j, count)rep(k, count)G[i][j] = min(G[i][j], G[i][k] + G[k][j]);cout << G[start][end] << endl;return 0;}