Untitled
unknown
plain_text
2 years ago
1.8 kB
13
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; }
Editor is loading...