Problem: Example

Input

4 2 1 1
1 2
3
4
3
1 2
2 4
3 4


Output

2 1

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


enum Type{
	A,
	B,
	C,
	None,
};

struct Info{
	Info(int arg_node_id,int arg_sum_dist,int arg_min_id){
		node_id = arg_node_id;
		sum_dist = arg_sum_dist;
		min_id = arg_min_id;
	}
	bool operator<(const struct Info &arg) const{ //移動距離の昇順(PQ)
		if(sum_dist != arg.sum_dist){
			return sum_dist > arg.sum_dist;
		}else{
			return min_id > arg.min_id;
		}
	}

	int node_id,sum_dist,min_id;
};

struct Data{
	int min_dist,min_id;
};

#define NUM 10000

int N,num[3],smallest_id[3];
Data min_data[3][NUM+3];
vector<int> G[NUM+3];
Type type[NUM];


//グループAorBorCの統合ノードからの、最短距離と、最短経路内の最小idを求める
void dijkstra(Type type){

	int first_smallest_id = min(smallest_id[A],min(smallest_id[B],smallest_id[C])); //A,B,Cは必ず集合に含むため

	for(int i = 0; i < N; i++){
		min_data[type][i].min_dist = BIG_NUM;
		min_data[type][i].min_id = first_smallest_id;
	}
	for(int i = 0; i < 3; i++){
		min_data[type][NUM+i].min_dist = BIG_NUM;
		min_data[type][NUM+i].min_id = first_smallest_id;
	}

	min_data[type][NUM+type].min_dist = 0;

	priority_queue<Info> Q;
	Q.push(Info(NUM+type,0,first_smallest_id));

	int next_node,next_cost,next_min_id;

	while(!Q.empty()){

		if(Q.top().sum_dist > min_data[type][Q.top().node_id].min_dist
				|| Q.top().min_id > min_data[type][Q.top().node_id].min_id){ //非最短コストまたは非最小idならSKIP
			Q.pop();
		}else{

			for(int i = 0; i < G[Q.top().node_id].size(); i++){
				next_node = G[Q.top().node_id][i];
				next_cost = Q.top().sum_dist+1;

				next_min_id = min(Q.top().min_id,next_node); //★最短経路中の最小id

				if(min_data[type][next_node].min_dist > next_cost){

					min_data[type][next_node].min_dist = next_cost;
					min_data[type][next_node].min_id = next_min_id;
					Q.push(Info(next_node,next_cost,next_min_id));

				}else if(min_data[type][next_node].min_dist == next_cost){

					if(min_data[type][next_node].min_id > next_min_id){
						min_data[type][next_node].min_id = next_min_id;
						Q.push(Info(next_node,next_cost,next_min_id));
					}
				}
			}
			Q.pop();
		}
	}
}

int main(){

	scanf("%d %d %d %d",&N,&num[A],&num[B],&num[C]);

	for(int i = 0; i < N; i++)type[i] = None;

	for(int i = 0; i < 3; i++)smallest_id[i] = BIG_NUM;

	int tmp_id;

	for(int loop = 0; loop < num[A]; loop++){
		scanf("%d",&tmp_id);
		tmp_id--;
		type[tmp_id] = A;
		smallest_id[A] = min(smallest_id[A],tmp_id);
	}

	for(int loop = 0; loop < num[B]; loop++){
		scanf("%d",&tmp_id);
		tmp_id--;
		type[tmp_id] = B;
		smallest_id[B] = min(smallest_id[B],tmp_id);
	}

	for(int loop = 0; loop < num[C]; loop++){
		scanf("%d",&tmp_id);
		tmp_id--;
		type[tmp_id] = C;
		smallest_id[B] = min(smallest_id[B],tmp_id);
	}

	int E;
	scanf("%d",&E);

	int from,to;

	for(int loop = 0; loop < E; loop++){
		scanf("%d %d",&from,&to);
		from--;
		to--;

		if(type[from] != type[to]){

			if(type[from] != None)from = NUM+type[from]; //A,B,Cはそれぞれまとめる
			if(type[to] != None)to = NUM+type[to];

			G[from].push_back(to);
			G[to].push_back(from);
		}else{ //type[from] == type[to]
			if(type[from] != None)continue; //A,B,Cの同じグループ内のエッジなら無視

			//学会に入っていない2人になるはず
			G[from].push_back(to);
			G[to].push_back(from);
		}
	}

	dijkstra(A);
	dijkstra(B);
	dijkstra(C);

	int ans_dist = BIG_NUM,ans_id = BIG_NUM,tmp_dist;

	for(int i = 0; i < NUM+3; i++){
		if(G[i].size() == 0)continue; //A,B,CのいずれかのノードならSKIP

		tmp_dist = min_data[A][i].min_dist+min_data[B][i].min_dist+min_data[C][i].min_dist;
		tmp_id = min(min_data[A][i].min_id,min(min_data[B][i].min_id,min_data[C][i].min_id));

		if(ans_dist > tmp_dist){

			ans_dist = tmp_dist;
			ans_id = tmp_id;

		}else if(ans_dist == tmp_dist){

			ans_id = min(ans_id,tmp_id);
		}
	}

	printf("%d %d\n",ans_dist,ans_id+1);

	return 0;
}