Untitled

 avatar
unknown
plain_text
2 years ago
1.8 kB
5
Indexable
#include<iostream>

using namespace std;

#define IFN	1000000

int N, M, H;

int root[1005];
int matrix[1005][1005];

int Queue[1005];
int front, rear;

int visit[1005];

void init() {
	front = rear = -1;
}

void push(int element) {
	Queue[++rear] = element;
}

int pop() {
	return Queue[++front];
}

bool isEmpty() {
	return front == rear;
}

void reset() {
	for (int i = 0; i < N; i++) {
		visit[i] = IFN;
		for (int j = i; j < N; j++)
			matrix[i][j] = matrix[j][i] = 0;
	}
}

void BFS(int start) {
	init();
	push(start);
	visit[start] = 0;

	while (!isEmpty()) {
		int top = pop();
		for (int i = 0; i < N; i++) {
			if (matrix[top][i] == 1) {
				if (visit[i] == IFN) {
					push(i);						// nếu hòn đảo chưa được tính độ yếu điện
					visit[i] = visit[top] + 1;
				} else if (visit[i] > visit[top] + 1) {
					push(i);						// nếu hòn đảo đã đc tính độ yếu điện nhưng độ yếu điện mới nhỏ hơn
					visit[i] = visit[top] + 1;
				}
			}
		}
	}
}

int main() {
	int T;
	//freopen("sample_input.txt", "r", stdin);
	cin >> T;

	for (int tc = 1; tc <= T; tc++) {
		cin >> N >> M >> H;

		for (int i = 0; i < M; i++)
			cin >> root[i];

		int ans = 0;
		reset();
		int u, v;
		for (int i = 0; i < H; i++) {
			cin >> u >> v;
			matrix[u][v] = matrix[v][u] = 1;		// tạo ma trận kề
		}

		for (int i = 0; i < M; i++)					// BFS tại các hòn đảo có đặt máy phát điện
			BFS(root[i]);
		
		int maX = -1;								// tìm hòn đảo có độ yếu điện lớn nhất
		for (int i = 0; i < N; i++) {
			if (visit[i] > maX) {
				maX = visit[i];
				ans = i;
			}
		}

		cout << ans << endl;
	}
	return 0;
}