hethongdiencode

 avatar
user_9278292
plain_text
a year ago
1.6 kB
3
Indexable
import java.util.Scanner;

public class Solution {

	static class Queue {
		int h, t, s;
		int[] a;

		Queue(int n) {
			h = t = s = 0;
			a = new int[n];
		}

		void enqueue(int x) {
			a[t++] = x;
			t %= a.length;
			s++;
		}

		int dequeue() {
			int x = a[h++];
			h %= a.length;
			s--;
			return x;
		}

		boolean isEmpty() {
			return s == 0;
		}
	}

	static int M, N, H, MAX = 10000000;
	static int[] power;
	static int[] weakPoint;
	static int[][] a;
	static Queue q;

	static void solve() {
		while (!q.isEmpty()) {
			int x = q.dequeue();
			for (int i = 0; i < N; i++) {
				if (a[x][i] == 1 && weakPoint[i] > weakPoint[x] + 1) {
					
					weakPoint[i] = weakPoint[x] + 1;
					q.enqueue(i);
				}
			}
		}
	}

    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tcs = sc.nextInt();
		for (int tc = 1; tc <= tcs; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			H = sc.nextInt();
			power = new int[M];
			weakPoint = new int[N];
			for (int i = 0; i < N; i++) {
				weakPoint[i] = MAX;
			}
			q = new Queue(N * N * 2);
			for (int i = 0; i < M; i++) {
				power[i] = sc.nextInt();
				weakPoint[power[i]] = 0;
				q.enqueue(power[i]);
			}
			
			a = new int[N][N];
			for (int i = 0; i < H; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				a[x][y] = 1;
				a[y][x] = 1;
			}

			solve();
			int id = 0;
			for (int i = 0; i < N; i++) {
				if (weakPoint[id] < weakPoint[i]) {
					id = i;
				}
			}
			System.out.println(id);
		}
	}
}
Leave a Comment