글 읽기 - PriorityQueue+다익스트라 구현 하였는데 어디서 틀렸는지 모르겠습니다.

kwonyg06 6년 전 0

PriorityQueue+다익스트라 구현 하였는데 어디서 틀렸는지 모르겠습니다.

혹시 로직상의 문제인지, 빠진 테스트 케이스가 있는지 고수님들의 조언 부탁드립니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int T,N,M,K;
	static int[] dist;
	static ArrayList<Travel>[] ticket;
	static final int MAX = 1000000000;
	static class Travel implements Comparable<Travel>{
		int v,c,d;
		Travel(int v,int c,int d){
			this.v = v;
			this.c = c;
			this.d = d;
		}
		@Override
		public int compareTo(Travel o) {
			return this.d-o.d;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc < T+1; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			ticket = new ArrayList[N+1];
			dist = new int[N+1];
			for (int i = 1; i < N+1; i++) {
				ticket[i] = new ArrayList<>();
			}
			Arrays.fill(dist, MAX);
			
			for (int i = 0; i < K; i++) {
				st = new StringTokenizer(br.readLine());
				int u = Integer.parseInt(st.nextToken());
				int v = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				int d = Integer.parseInt(st.nextToken());
				ticket[u].add(new Travel(v, c, d));
			}
			dijkstra();
			System.out.println(dist[N] >= MAX? "Poor KCM":  dist[N]);
		}
		br.close();
	}
	
	public static void dijkstra() {
		PriorityQueue<Travel> pq = new PriorityQueue<>();
		pq.add(new Travel(1, 0, 0));
		dist[1] = 0;

		while(!pq.isEmpty()){
			Travel tv = pq.poll();

			for(Travel next:ticket[tv.v]){
				if(tv.c + next.c <= M && 
						dist[next.v]> tv.d+next.d){
						dist[next.v]= tv.d+next.d;
					pq.add(new Travel(next.v, tv.c + next.c, dist[next.v]));
				}
			}
		}		
	}
}

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

문제

문제

출처

ICPC

PriorityQueue+다익스트라 구현 하였는데 어디서 틀렸는지 모르겠습니다.

kwonyg06 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말