結果

問題 No.859 路線A、路線B、路線C
ユーザー ahe100ahe100
提出日時 2019-08-09 22:05:36
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 2,694 bytes
コンパイル時間 1,766 ms
コンパイル使用メモリ 175,060 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-26 18:07:34
合計ジャッジ時間 2,575 ms
ジャッジサーバーID
(参考情報)
judge12 / judge11
このコードへのチャレンジ(β)

テストケース

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

ソースコード

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