글 읽기 - 1005-ACM Craft (Java) 반례 부탁드립니다 ㅠ

ssshhh0402 3년 전 0

기본적으로 Queue를 이용하여 위상정렬 알고리즘으로 문제를 해결하려 했습니다. 다른 사람들의 경우 다익스트라처럼 걸리는 시간(?)을 배열에다가 저장해 놓던데 저는 Queue에다가 여태까지 건설에 필요한 시간을 같이 넣어서 계산하였습니다. 기본 테케나 게시판에 있는 반례는 다 맞게 나오는거같은데 채점에선 계속해서 틀렸다고 나오네여 ㅠ.. 제가 어느부분을 놓쳤는지 모르겠습니다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class BJ_1005_ACM {
    static class Pair{
        int end, weight;
        Pair(int a, int b){
            this.end = a;
            this.weight = b;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int N, M, answer;
        ArrayList<Integer>[] base;
        int [] count, times;
        Queue<Pair> q;
        String[] inputs;

        while(T -- > 0){
            answer = Integer.MIN_VALUE;
            inputs = br.readLine().split(" ");
            N = Integer.parseInt(inputs[0]);
            M = Integer.parseInt(inputs[1]);
            base = new ArrayList[N+1];
            count = new int[N+1];
            times = new int[N+1];
            q = new LinkedList<Pair>();
            for(int i = 1; i < N+1; i++){
                base[i] = new ArrayList<Integer>();
            }
            inputs = br.readLine().split(" ");
            for(int i = 0; i < N; i++){
                times[i+1] = Integer.parseInt(inputs[i]);
            }
            for(int i = 0 ; i < M; i++){
                inputs = br.readLine().split(" ");
                int start = Integer.parseInt(inputs[0]);
                int end = Integer.parseInt(inputs[1]);
                base[start].add(end);
                count[end] += 1;
            }
            int W = Integer.parseInt(br.readLine());
            for(int i = 1; i < N+1; i++){
                if(count[i] == 0){
                    q.add(new Pair(i, times[i]));
                }
            }
            while(!q.isEmpty()){
                Pair now = q.poll();
                if(now.end == W){
                    answer = Math.max(now.weight, answer);
                    continue;
                }
                for(int toGo : base[now.end]){
                    count[toGo] -= 1;
                    if(count[toGo] == 0){
                        q.add(new Pair(toGo, now.weight + times[toGo]));
                    }
                }
            }
            System.out.println(answer);
        }
    }
}

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

문제

문제

출처

ICPC

1005-ACM Craft (Java) 반례 부탁드립니다 ㅠ

ssshhh0402 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말