제출 #726985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
726985		rahulverma	Bosses (BOI16_bosses)	Java	67 / 100	1552 ms	14808 KiB

bosses

import java.io.*;
import java.util.*;

public class bosses {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
		for(int i = 0; i < n; i++) graph.add(new ArrayList<Integer>());
		for(int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int k = Integer.parseInt(st.nextToken());
			for(int j = 0; j < k; j++) {
				int v = Integer.parseInt(st.nextToken()) - 1;
				graph.get(v).add(i);
			}
		}
		
		int ans = Integer.MAX_VALUE;
		for(int i = 1; i < n; i++) {
			int cur = 1;
			Queue<Integer> q = new LinkedList<>();
			q.add(i);
			int[] dist = new int[n];
			dist[i] = 1;
			int numReached = 0;
			while(!q.isEmpty() && numReached != n) {
				numReached++;
				int node = q.poll();
				for(int node2: graph.get(node)) {
					if(dist[node2] == 0) {
						cur += dist[node] + 1;
						dist[node2] = dist[node] + 1;
						q.add(node2);
					}
				}
			}
			boolean reached = false;
			if(numReached == n) reached = true;
			if(reached) ans = Math.min(ans,  cur);
		}
		PrintWriter pw = new PrintWriter(System.out);
		pw.println(ans);
		pw.close();
	}

}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 0 / 33