He thong dien

Level 4
Hệ thống điện
Hệ thống điện

Sau khi anh VenG đã xây dựng đường đi giữa những hòn đảo, anh Eagle được cử sang để xây dựng hệ thống điện giữa các hòn đảo cho người dân, do muốn ăn bớt kinh phí nên anh Eagle không xây dựng trạm phát điện trên tất cả các đảo mà chỉ xây trên 1 số đảo nhất định. Các đảo kết nối với nhau thành 1 mạng lưới điện. Rõ ràng những đảo nào ở càng xa nguồn phát thì điện sẽ càng yếu.

Để đảm bảo người dân không than phiền điện yếu, nên anh Eagle muốn tính toán xem điện ở đảo nào sẽ yếu nhất.

Độ yếu của điện tại đảo X được tính bằng 0 nếu đảo đó có trạm phát điện, nếu đảo X có kết nối điện với đảo Y mà đảo Y ở gần trạm phát hơn, độ yếu tại đảo X = độ yếu tại đảo Y + 1. Nếu đảo X không có điện thì có độ yếu bằng vô cùng (infinity).

Input

Dòng đầu tiên chứa số testcase T.

Mỗi test case gồm:

Dòng đầu tiên gồm 3 số nguyên N, M, H lần lượt là số đảo, M là số đảo có trạm phát điện, H là số kết nối 2 chiều. (N, M <= 1 000, H <= 10 000).

Dòng tiếp theo gồm M số là ID các đảo có máy phát điện (ID đánh số từ 0 tới N-1).

H dòng tiếp theo, mỗi dòng gồm 2 số u, v, cho biết đảo u có kết nối với đảo v.

 

Output

In ra đảo độ yếu của điện là cao nhất. Nếu có nhiều đáp án, in ra đảo có ID nhỏ nhất.

Example

Input:

2

6 3 5

0 5 2

0 1

1 2

4 5

3 5

0 2

6 2 3

5 2

0 5

0 1

3 4

 

Output:

 

1

3

1
0
0
1
9
9
0
0
3
160
259
100
1
999
796
Time: 0.46300 s.

#include <iostream>
#include <time.h>

using namespace std;

int oo = 2000000000;

int T, n, m, h, result, maxx;
int arr[1001][2], a[1001], mp[1001][1001], vs[1001];

int head, tail, q[1000001];

void bfs(int index){
	head = 0, tail = 0;
	q[tail++] =  index;

	while(head != tail){
		int x = q[head];

		head++;

		for(int i = 0; i < n; i++){
			if(mp[x][i] == 1 && vs[i] > vs[x] + 1){
				vs[i] = vs[x] + 1;
				q[tail++] = i;
			}
		}
	}
}

int main(){
	// read input
	freopen("input.txt", "r", stdin);

	//calc time
	clock_t tStart, tStop;
	tStart = clock();

	cin >> T;
	
	for(int tc = 1; tc <= T; tc++){
		// input and initial
		cin >> n >> m >> h;

		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				mp[i][j] = 0;
			}
			vs[i] = oo;
		}

		for(int i = 0; i < m; i++){
			cin >> a[i];
			vs[a[i]] = 0;
		}

		for(int i = 0; i < h; i++){
			int x, y;
			cin >> x >> y;
			mp[x][y] = 1, mp[y][x] = 1;
		}
		result = oo, maxx = -1;

		// solve problem
		if(m == n){
			result = 0;
		} else{
			for(int i = 0; i < m; i++){
				bfs(a[i]);
			}
			for(int i = 0; i < n; i++){
				if((maxx < vs[i]) || (maxx == vs[i] && result > i)){
					result = i, maxx = vs[i];
				} 
			}
		}

		// output
		cout << result << endl;
	}


	//calc time
	tStop = clock();
	cout.setf(ios::fixed);
	cout.precision(5);
	cout << "Time: " << double(tStop - tStart) / CLOCKS_PER_SEC << " s." << endl;

	return 0;
}