글 읽기 - 어느 부분이 틀렸는지 도저히 모르겠습니다...

zkdlajt1 2년 전 0

반례를 찾아서 대입해봐도 답이 잘 나오는데 틀리는 원인을 모르겠습니다.

위상정렬의 알고리즘을 참고해서 풀었습니다. 다만, 일반적인 큐가 아닌 우선순위 큐에 indegree가 0인 정점을 넣어주고, 우선순위 큐에서 Delay가 최소인 정점을 꺼내면서 그 정점과 연결된 indegree를 줄여준 뒤 다시 indegree가 0이 된 정점을 우선순위 큐에 넣어주는 방식입니다. 물론 우선순위큐에 이전에 들어있던 정점의 Delay시간도 매 순간 줄여주었습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws Exception {
		
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < T; i++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			
			int[] delay = new int[N + 1];
			List<Integer> link[] = new List[N + 1]; //인접리스트
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 1; j <= N; j++) {
				delay[j] = Integer.parseInt(st.nextToken());
				link[j] = new ArrayList<Integer>();
			}
			
			int[] inDegree = new int[N + 1];
			for (int j = 0; j < K; j++) {
				st = new StringTokenizer(br.readLine(), " ");
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());
				
				link[from].add(to);
				inDegree[to]++;
			}
			
			int W = Integer.parseInt(br.readLine());
			
			int time = -1;
			PriorityQueue<Building> pq = new PriorityQueue<>();
			for (int j = 1; j <= N; j++) {
				if (inDegree[j] == 0) {
					if (j == W) {
						time = delay[W];
						break;
					}
					
					inDegree[j]--;
					pq.offer(new Building(j, delay[j]));
				}
			}
			if (time == -1) {
				time = 0;
				Queue<Building> q = new LinkedList<>();
out:			while (!pq.isEmpty()) {
					int minTime = -1;
					int size = pq.size();
					
					for (int j = 0; j < size; j++) {
						Building del = pq.poll();
						if (minTime == -1)
							minTime = del.time;
						
						del.time -= minTime;
						if (del.time > 0) {
							q.offer(del);
							continue;
						}
						
						time += minTime;
						for (Integer to : link[del.num]) {
							if (--inDegree[to] == 0) {
								if (to == W) {
									time += delay[W];
									break out;
								}
								--inDegree[to];
								q.offer(new Building(to, delay[to]));
							}
						}
					}
					
					while (!q.isEmpty())
						pq.offer(q.poll());
				}
			}
			sb.append(time).append("\n");
		}
		
		System.out.print(sb.toString());
	}//end main
	
	static class Building implements Comparable<Building> {
		int num;
		int time;
		
		public Building(int num, int time) {
			super();
			this.num = num;
			this.time = time;
		}
		
		@Override
		public int compareTo(Building o) {
			return time - o.time;
		}
	}
}

zkdlajt1 2년 전 0

PQ에 time값이 같은 게 있을 경우 문제가 생기는 거였습니다... 75번 줄의 time += minTime; 부분을 66번의 if문 안에 넣어주면 해결되었습니다. 58%에서 틀리신다면 시간이 가장 적게 남은 건물이 여러 개 있는 경우를 고려해보시면 좋을 것 같습니다.

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

문제

문제

출처

ICPC

어느 부분이 틀렸는지 도저히 모르겠습니다...

zkdlajt1 2년 전 0

zkdlajt1 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말