제출 #1263017

#제출 시각아이디문제언어결과실행 시간메모리
1263017vampirrBosses (BOI16_bosses)Java
100 / 100
1198 ms157084 KiB
import java.util.*;
public class bosses {
	
	static int N;
	static ArrayList<Integer>[] adjlist;
	static int cost,nodesvisited;
	static int[] depth;
	
	public static void bfs(int start) {
		depth = new int[N+1];
		depth[start]=1;
		Deque<Integer> q = new ArrayDeque<Integer>();
		q.add(start);
		cost=1;
		while (!q.isEmpty()) {
			nodesvisited++;
			int curr = q.poll();
			for (int other : adjlist[curr]) {
				if (depth[other]==0) {
					depth[other]=depth[curr]+1;
					cost+=depth[other];
					q.add(other);
				}
			}
		}
		
	}
	
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		N = in.nextInt();
		adjlist = new ArrayList[N+1];
		for (int i=0; i<=N; i++) {
			adjlist[i]=new ArrayList<Integer>();
		}
		for (int i=1; i<=N; i++) {
			int k = in.nextInt();
			while (k-->0) {
				int a = in.nextInt();
				adjlist[a].add(i);
			}
		}
		in.close();
		int ans=Integer.MAX_VALUE;
		for (int i=1; i<=N; i++) {
			nodesvisited=0;
			bfs(i);
			if(nodesvisited == N) {
				ans = Math.min(cost, ans);
			}
		}
		System.out.println(ans);

	}

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...