Untitled

 avatar
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