3767 I Wanna Go Home

問題概要

重み付き無向グラフで表わされる都市と道路がある。
都市1から都市2へ最短距離で帰りたい。

この国では内戦がおきて、それぞれの都市はリーダー1またはリーダー2のどちらかを支持している。
安全のために、リーダーの異なる都市への移動は一度だけにしたい。
また、都市1のリーダーは1、都市2のリーダーは2であることがわかっている。

移動しなければならない距離を求めよ。
条件を満たして都市1から都市2へ帰ることができないとき、-1を出力せよ。

解法

リーダーが違う都市間の移動は最大1回、
かつ出発の都市はリーダー1で、到着の都市はリーダー2であるため、
一度1から2の都市に移動したら2から1の都市へ戻ることはできないことがわかる。

すなわち、元のグラフで2->1の辺はすべて削除した上でダイクストラ法をすれば良い。

ソースコード

int n,m,l[600];
int a[10000],b[10000],c[10000];
vector<vector<pair<int,int> > > e;

int func(){
	bool v[600]={0};
	priority_queue<pair<int,int> > Q; Q.push(mp(0,0));
	while(!Q.empty()){
		int c=Q.top().second,cc=Q.top().first; Q.pop();
		if(v[c])continue;
		v[c]=1; if(c==1)return -cc;
		
		fr(i,e[c])if(!v[i->first])Q.push(mp(cc-i->second,i->first));
	}
	return -1;
}
int main(){
	while(scanf("%d",&n),n){
		e.clear(); e.resize(n);
		scanf("%d",&m);
		rep(i,m)scanf("%d%d%d",a+i,b+i,c+i);
		rep(i,n)scanf("%d",l+i);
		
		rep(i,m){
			int x=a[i]-1,y=b[i]-1,z=c[i];
			if(l[x]!=l[y]){
				if(l[x]==2)swap(x,y);
				e[x].pb(mp(y,z));
			}
			else e[x].pb(mp(y,z)),e[y].pb(mp(x,z));
		}
		printf("%d\n",func());
	}
	return 0;
}