結果

問題 No.859 路線A、路線B、路線C
ユーザー okok
提出日時 2019-08-09 22:43:19
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 6,474 bytes
コンパイル時間 1,422 ms
コンパイル使用メモリ 89,948 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-19 14:47:52
合計ジャッジ時間 1,877 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = (long long)1e9 + 7; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}


#define MAX_VAL 100
#define to first
#define cost second

typedef long long ll;
typedef pair<ll,ll> P;

// struct edge{ll to, cost;};

vector<pair<int,int>> G[MAX_VAL];
ll d[MAX_VAL], V;

void dijkstra(ll s){
	priority_queue<P,vector<P>,greater<P>> q;
	fill(d,d+V, INF);
	
	d[s] = 0;
	q.push(P(0,s));
	
	while(!q.empty()){
		P p = q.top();q.pop();
		ll v = p.second;
		
		if(d[v] < p.first) continue;
		
		for(pair<int,int> e : G[v]){
			if(d[e.to] > d[v] + e.cost){
				d[e.to] = d[v] + e.cost;
				q.push(P(d[e.to],e.to));
			}
		}
	}	
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int x, y, z;
	int ans = 0;
	char s1, s0;
	int t0, t1;
	
	V = 10;
	
	cin>>x>>y>>z;
	cin>>s0>>t0>>s1>>t1;
	
	x *= 2, y *= 2, z *= 2;
	
	if(s0 == 'A'){
		if(s1 == 'A'){
			G[2].push_back(make_pair(3,y));
			G[3].push_back(make_pair(2,y));
			G[2].push_back(make_pair(3,z));
			G[3].push_back(make_pair(2,z));
			
			if(t0 < t1){
				G[2].push_back(make_pair(0,(t0-1)*2 + 1));
				G[0].push_back(make_pair(2,(t0-1)*2 + 1));
				
				G[0].push_back(make_pair(1,(t1-t0)*2));
				G[1].push_back(make_pair(0,(t1-t0)*2));
				
				G[1].push_back(make_pair(3,(x/2-t1)*2 + 1));
				G[3].push_back(make_pair(1,(x/2-t1)*2 + 1));
			} else {
				G[2].push_back(make_pair(1,(t1-1)*2 + 1));
				G[1].push_back(make_pair(2,(t1-1)*2 + 1));
				
				G[1].push_back(make_pair(0,(t0-t1)*2));
				G[0].push_back(make_pair(1,(t0-t1)*2));
				
				G[0].push_back(make_pair(3,(x/2-t0)*2 + 1));
				G[3].push_back(make_pair(0,(x/2-t0)*2 + 1));
			}
		} else if(s1 == 'B'){
			G[2].push_back(make_pair(3,z));
			G[3].push_back(make_pair(2,z));
			
			G[2].push_back(make_pair(0,(t0-1)*2 + 1));
			G[0].push_back(make_pair(2,(t0-1)*2 + 1));
			
			G[0].push_back(make_pair(3,(x/2-t0)*2 + 1));
			G[3].push_back(make_pair(0,(x/2-t0)*2 + 1));
			
			
			G[2].push_back(make_pair(1,(t1-1)*2 + 1));
			G[1].push_back(make_pair(2,(t1-1)*2 + 1));
			
			G[1].push_back(make_pair(3,(y/2-t1)*2 + 1));
			G[3].push_back(make_pair(1,(y/2-t1)*2 + 1));
		} else {
			G[2].push_back(make_pair(3,y));
			G[3].push_back(make_pair(2,y));
			
			G[2].push_back(make_pair(0,(t0-1)*2 + 1));
			G[0].push_back(make_pair(2,(t0-1)*2 + 1));
			
			G[0].push_back(make_pair(3,(x/2-t0)*2 + 1));
			G[3].push_back(make_pair(0,(x/2-t0)*2 + 1));
			
			
			G[2].push_back(make_pair(1,(t1-1)*2 + 1));
			G[1].push_back(make_pair(2,(t1-1)*2 + 1));
			
			G[1].push_back(make_pair(3,(z/2-t1)*2 + 1));
			G[3].push_back(make_pair(1,(z/2-t1)*2 + 1));
			
		}
	} else if(s0 == 'B'){
		if(s1 == 'A'){
			G[2].push_back(make_pair(3,z));
			G[3].push_back(make_pair(2,z));
			
			G[2].push_back(make_pair(0,(t0-1)*2 + 1));
			G[0].push_back(make_pair(2,(t0-1)*2 + 1));
			
			G[0].push_back(make_pair(3,(y/2-t0)*2 + 1));
			G[3].push_back(make_pair(0,(y/2-t0)*2 + 1));
			
			
			G[2].push_back(make_pair(1,(t1-1)*2 + 1));
			G[1].push_back(make_pair(2,(t1-1)*2 + 1));
			
			G[1].push_back(make_pair(3,(x/2-t1)*2 + 1));
			G[3].push_back(make_pair(1,(x/2-t1)*2 + 1));
		} else if(s1 == 'B'){
			G[2].push_back(make_pair(3,x));
			G[3].push_back(make_pair(2,x));
			G[2].push_back(make_pair(3,z));
			G[3].push_back(make_pair(2,z));
			
			if(t0 < t1){
				G[2].push_back(make_pair(0,(t0-1)*2 + 1));
				G[0].push_back(make_pair(2,(t0-1)*2 + 1));
				
				G[0].push_back(make_pair(1,(t1-t0)*2));
				G[1].push_back(make_pair(0,(t1-t0)*2));
				
				G[1].push_back(make_pair(3,(y/2-t1)*2 + 1));
				G[3].push_back(make_pair(1,(y/2-t1)*2 + 1));
			} else {
				G[2].push_back(make_pair(1,(t1-1)*2 + 1));
				G[1].push_back(make_pair(2,(t1-1)*2 + 1));
				
				G[1].push_back(make_pair(0,(t0-t1)*2));
				G[0].push_back(make_pair(1,(t0-t1)*2));
				
				G[0].push_back(make_pair(3,(y/2-t0)*2 + 1));
				G[3].push_back(make_pair(0,(y/2-t0)*2 + 1));
			}
		} else {
			G[2].push_back(make_pair(3,x));
			G[3].push_back(make_pair(2,x));
			
			G[2].push_back(make_pair(0,(t0-1)*2 + 1));
			G[0].push_back(make_pair(2,(t0-1)*2 + 1));
			
			G[0].push_back(make_pair(3,(y/2-t0)*2 + 1));
			G[3].push_back(make_pair(0,(y/2-t0)*2 + 1));
			
			
			G[2].push_back(make_pair(1,(t1-1)*2 + 1));
			G[1].push_back(make_pair(2,(t1-1)*2 + 1));
			
			G[1].push_back(make_pair(3,(z/2-t1)*2 + 1));
			G[3].push_back(make_pair(1,(z/2-t1)*2 + 1));
			
		}
	} else {
		if(s1 == 'A'){
			G[2].push_back(make_pair(3,y));
			G[3].push_back(make_pair(2,y));
			
			G[2].push_back(make_pair(0,(t0-1)*2 + 1));
			G[0].push_back(make_pair(2,(t0-1)*2 + 1));
			
			G[0].push_back(make_pair(3,(z/2-t0)*2 + 1));
			G[3].push_back(make_pair(0,(z/2-t0)*2 + 1));
			
			
			G[2].push_back(make_pair(1,(t1-1)*2 + 1));
			G[1].push_back(make_pair(2,(t1-1)*2 + 1));
			
			G[1].push_back(make_pair(3,(x/2-t1)*2 + 1));
			G[3].push_back(make_pair(1,(x/2-t1)*2 + 1));
		} else if(s1 == 'B'){
			G[2].push_back(make_pair(3,x));
			G[3].push_back(make_pair(2,x));
			
			G[2].push_back(make_pair(0,(t0-1)*2 + 1));
			G[0].push_back(make_pair(2,(t0-1)*2 + 1));
			
			G[0].push_back(make_pair(3,(z/2-t0)*2 + 1));
			G[3].push_back(make_pair(0,(z/2-t0)*2 + 1));
			
			
			G[2].push_back(make_pair(1,(t1-1)*2 + 1));
			G[1].push_back(make_pair(2,(t1-1)*2 + 1));
			
			G[1].push_back(make_pair(3,(y/2-t1)*2 + 1));
			G[3].push_back(make_pair(1,(y/2-t1)*2 + 1));
		} else {
			G[2].push_back(make_pair(3,x));
			G[3].push_back(make_pair(2,x));
			G[2].push_back(make_pair(3,y));
			G[3].push_back(make_pair(2,y));
			
			if(t0 < t1){
				G[2].push_back(make_pair(0,(t0-1)*2 + 1));
				G[0].push_back(make_pair(2,(t0-1)*2 + 1));
				
				G[0].push_back(make_pair(1,(t1-t0)*2));
				G[1].push_back(make_pair(0,(t1-t0)*2));
				
				G[1].push_back(make_pair(3,(z/2-t1)*2 + 1));
				G[3].push_back(make_pair(1,(z/2-t1)*2 + 1));
			} else {
				G[2].push_back(make_pair(1,(t1-1)*2 + 1));
				G[1].push_back(make_pair(2,(t1-1)*2 + 1));
				
				G[1].push_back(make_pair(0,(t0-t1)*2));
				G[0].push_back(make_pair(1,(t0-t1)*2));
				
				G[0].push_back(make_pair(3,(z/2-t0)*2 + 1));
				G[3].push_back(make_pair(0,(z/2-t0)*2 + 1));
			}
			
		}
		
	}
	dijkstra(0);
	
	cout<<d[1]/2<<endl;
	
	
	return 0;
}
0