結果

問題 No.859 路線A、路線B、路線C
コンテスト
ユーザー ahe100
提出日時 2019-08-09 22:05:36
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 1,000 ms
コード長 2,694 bytes
コンパイル時間 1,877 ms
コンパイル使用メモリ 177,504 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-19 12:06:02
合計ジャッジ時間 2,548 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)

/*
*/

void dijkstra(int root,vector<ll>& d,vector<ll> v[],vector<ll> c[],ll INF=1e18){
	queue<int> Q;
	rep(i,d.size())d[i]=INF;
	d[root]=0;
	Q.push(root);
	while(!Q.empty()){
		int p = Q.front();Q.pop();
		// cerr<<p<<endl;
		for(int i=0;i<v[p].size();i++){
			int q = v[p][i];
			ll cost=c[p][i];
			if(d[q]>d[p]+cost){
				d[q]=d[p]+cost;
				Q.push(q);
			}
		}
	}
}

ll x,y,z,t[2],ans=1e18;
vector<ll> v[10],c[10],d(10);
char s[2];

void init(){
	cin>>x>>y>>z;
	rep(i,2)cin>>s[i]>>t[i];
	if(t[0]>t[1]){
		swap(t[0],t[1]);
		swap(s[0],s[1]);
	}
	//
	if(t[0]<=x){
		v[0].push_back(1);
		c[0].push_back(2*t[0]-1);
		v[1].push_back(0);
		c[1].push_back(2*t[0]-1);
		if(t[1]<=x){
			v[1].push_back(2);
			v[2].push_back(1);
			c[1].push_back(2*(t[1]-t[0]));
			c[2].push_back(2*(t[1]-t[0]));
			v[2].push_back(7);
			v[7].push_back(2);
			c[2].push_back(2*(x-t[1])+1);
			c[7].push_back(2*(x-t[1])+1);
		}else{
			v[1].push_back(7);
			v[7].push_back(1);
			c[1].push_back(2*(x-t[0])+1);
			c[7].push_back(2*(x-t[0])+1);
		}
	}else{
		v[0].push_back(7);
		c[0].push_back(2*x+1);
		v[7].push_back(0);
		c[7].push_back(2*x+1);
	}
	//
	if(t[0]<=y){
		v[0].push_back(3);
		c[0].push_back(2*t[0]-1);
		v[3].push_back(0);
		c[3].push_back(2*t[0]-1);
		if(t[1]<=y){
			v[3].push_back(4);
			v[4].push_back(3);
			c[3].push_back(2*(t[1]-t[0]));
			c[4].push_back(2*(t[1]-t[0]));
			v[4].push_back(7);
			v[7].push_back(4);
			c[4].push_back(2*(y-t[1])+1);
			c[7].push_back(2*(y-t[1])+1);
		}else{
			v[3].push_back(7);
			v[7].push_back(3);
			c[3].push_back(2*(y-t[0])+1);
			c[7].push_back(2*(y-t[0])+1);
		}
	}else{
		v[0].push_back(7);
		c[0].push_back(2*y+1);
		v[7].push_back(0);
		c[7].push_back(2*y+1);
	}
	//
	if(t[0]<=z){
		v[0].push_back(5);
		c[0].push_back(2*t[0]-1);
		v[5].push_back(0);
		c[5].push_back(2*t[0]-1);
		if(t[1]<=z){
			v[5].push_back(6);
			v[6].push_back(5);
			c[5].push_back(2*(t[1]-t[0]));
			c[6].push_back(2*(t[1]-t[0]));
			v[6].push_back(7);
			v[7].push_back(6);
			c[6].push_back(2*(z-t[1])+1);
			c[7].push_back(2*(z-t[1])+1);
		}else{
			v[5].push_back(7);
			v[7].push_back(5);
			c[5].push_back(2*(z-t[0])+1);
			c[7].push_back(2*(z-t[0])+1);
		}
	}else{
		v[0].push_back(7);
		c[0].push_back(2*z+1);
		v[7].push_back(0);
		c[7].push_back(2*z+1);
	}
}

int main(void){
	init();
	ll root = (s[0]-'A')*2+1;
	dijkstra(root,d,v,c);
	cout<<d[(s[1]-'A')*2+2]/2<<endl;
	return 0;
}
0