#367157 (C++11) No.859 路線A、路線B、路線C

提出ソース
結果

問題	No.859 路線A、路線B、路線C
ユーザー	ok
提出日時	2019-08-09 22:43:19
言語	C++11 (gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 12
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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;
}
yukicoder

結果

ソースコード
