Untitled
unknown
plain_text
10 months ago
2.2 kB
4
Indexable
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int T = scanner.nextInt(); for (int t = 0; t < T; t++) { int N = scanner.nextInt(); int M = scanner.nextInt(); int H = scanner.nextInt(); int[] powerStations = new int[M]; for (int i = 0; i < M; i++) { powerStations[i] = scanner.nextInt(); } boolean[][] graph = new boolean[N][N]; for (int i = 0; i < H; i++) { int u = scanner.nextInt(); int v = scanner.nextInt(); graph[u][v] = true; graph[v][u] = true; } int[] weakness = new int[N]; for (int i = 0; i < N; i++) { weakness[i] = Integer.MAX_VALUE; } int[] queue = new int[N]; int front = 0, rear = 0; for (int i = 0; i < M; i++) { int powerStation = powerStations[i]; queue[rear++] = powerStation; weakness[powerStation] = 0; } while (front < rear) { int current = queue[front++]; for (int neighbor = 0; neighbor < N; neighbor++) { if (graph[current][neighbor] && weakness[neighbor] == Integer.MAX_VALUE) { weakness[neighbor] = weakness[current] + 1; queue[rear++] = neighbor; } } } int maxWeakness = -1; int islandWithMaxWeakness = -1; for (int i = 0; i < N; i++) { if (weakness[i] > maxWeakness) { maxWeakness = weakness[i]; islandWithMaxWeakness = i; } else if (weakness[i] == maxWeakness && i < islandWithMaxWeakness) { islandWithMaxWeakness = i; } } System.out.println(islandWithMaxWeakness); } scanner.close(); } }
Editor is loading...
Leave a Comment