글 읽기 - 1005번 33%에서 틀립니다. 반례가 뭘까요 ㅜㅜ

lsm941010 5년 전 0

게시판에 있던 앞선 테스트케이스를 해 본 결과 맞게 나오나 33%에서 계속적으로 틀립니다.

어느 부분에서 틀렸는지 알 수 있을까요 ㅜㅜㅜㅜ

코드는 BFS 기반으로 문제를 풀었습니다.

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = Integer.parseInt(br.readLine());
		
		while(testCase-- > 0) {
			Craft c = new Craft(br);
			c.getCraftTimes();
		}
		
		br.close();
	}

}

class Craft{
	private int total, rules, winBuild;
	private int []time;
	private boolean [][] board, visit;
	private Queue<Integer> q;
	private int[] tb;
	
	public Craft(BufferedReader br) throws IOException{
		String temp = br.readLine();
		String[] tok = temp.split(" ");
		
		total = Integer.parseInt(tok[0]);
		rules = Integer.parseInt(tok[1]);
		
		time = new int[total + 1];
		temp = br.readLine();
		tok = temp.split(" ");

		for(int i = 1; i <= total; i++) {
			time[i] = Integer.parseInt(tok[i-1]);
		}
		
		board = new boolean[total+1][total+1];
		q = new LinkedList<Integer>();
		
		tb = new int[total + 1];
		for(int i = 0; i < rules; i++) {
			temp = br.readLine();
			tok = temp.split(" ");
			board[Integer.parseInt(tok[0])][Integer.parseInt(tok[1])] = true;	
		}
		
		winBuild = Integer.parseInt(br.readLine());
	}
	
	public void getCraftTimes() {
		visit = new boolean[total + 1][total + 1];
		for(int i = 1; i <= total; i++ ) {
			tb[i] = time[i];
			int cnt = 0;
			for(int j = 1; j <= total; j++) {
				if(board[j][i]) cnt++;
			}
			
			if(cnt == 0) {
				q.add(i);
			}
		}
				
		while(!q.isEmpty()) {
			int row = q.poll();
			
			//if(row == winBuild) break;
			
			for(int i = 1; i <= total; i++) {
				if(board[row][i] && !visit[row][i]) {
					q.add(i);
					visit[row][i] = true;
					tb[i] = Math.max(tb[i], tb[row] + time[i]);
				    //System.out.println(row+" "+i+" "+tb[i]);
				}
			}
		}
		
		System.out.println(tb[winBuild]);
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1005번 33%에서 틀립니다. 반례가 뭘까요 ㅜㅜ

lsm941010 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말