Benelux Algorithm Programming Contest > BAPC 2018 D번

Driver_Disagreement.cpp

#include <stdio.h>
#include <vector>
#include <queue>
#define M 100009
using namespace std;
struct pp{
	int a,b,d;
	pp(){};
	pp(int _a, int _b, int _d){ a=_a; b=_b; d=_d; }
};

int n, A, B, left[M], right[M], p[M], parent[M];
queue<pp> q;
int get_parent(int a){
	if (a == parent[a]) return a;
	return parent[a] = get_parent(parent[a]);
}
int main(){
	int i;
	scanf("%d %d %d",&n, &B, &A);
	for (i=0;i<n;i++) scanf("%d %d %d",&left[i], &right[i], &p[i]);
	for (i=0;i<n;i++) parent[i]=i;
	q.push(pp(A,B,0));
	while(!q.empty()){
		pp here = q.front(); q.pop();
		if (p[here.a] + p[here.b] == 1){
			printf("%d\n", here.d);
			return 0;
		}
		else if (get_parent(here.a) == get_parent(here.b)) continue;
		parent[get_parent(here.a)] = get_parent(here.b);
		q.push(pp(left[here.a], left[here.b], here.d+1));
		q.push(pp(right[here.a], right[here.b], here.d+1));
	}
	printf("indistinguishable\n");
}