KCM Travel_ 집단지성의 힘을 믿습니다.

[yess98]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Airport implements Comparable<Airport>{
	int to; 
	int cost; 
	int time; 
	public Airport (int to , int c, int t)
	{
		this.to = to ; 
		this.cost = c; 
		this.time = t; 
		
	}
	public Airport () {
		
	}
	@Override
	public int compareTo(Airport a ) {
		if (this.time == a.time) {
			return this.cost - a.cost; 
		}
		return this.time - a.time; 
	}
	
	
}
public class Main {
	static ArrayList <Airport>[] airport ; 
	static int t; 
	static int n ; 
	static int m ; 
	static int k ; 
	static int cost[]; 
	static int time [] ; 
	static PriorityQueue <Airport> pq ; 
	
	public static void main(String [] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader (System.in)); 
		StringTokenizer st ; 
		StringBuilder sb = new StringBuilder(); 
		t = Integer.parseInt(br.readLine()); 
		for(int  i = 0 ; i < t; i ++)
		{
			st = new StringTokenizer(br.readLine()); 
			n = Integer.parseInt(st.nextToken()); 
			m = Integer.parseInt(st.nextToken()); 
			k = Integer.parseInt(st.nextToken()); 
			airport = new ArrayList[n +1 ]; 
			cost =new int[n +1 ]; 
			time = new int [n + 1]; 
			Arrays.fill(cost,Integer.MAX_VALUE); 
			Arrays.fill(time, Integer.MAX_VALUE);
			
			for(int t = 1; t <= n ; t ++) {
				airport[t] = new ArrayList <Airport >(); 
			}
			 
			pq = new PriorityQueue<>(); 
			for(int j  = 0 ; j < k ;  j ++) {
				st = new StringTokenizer(br.readLine()); 
				int from = Integer.parseInt(st.nextToken()); 
				int to  = Integer.parseInt(st.nextToken()); 
				int cost = Integer.parseInt(st.nextToken()); 
				int time = Integer.parseInt(st.nextToken()); 
				airport[from].add(new Airport(to,cost, time)); 
				
			}

			Dijkstra(1, 0, 0); 
			if (cost[n] <=  m) {
				sb.append(time[n] + "\n");
			}
			else {
				sb.append("Poor KCM\n");
			}
		}
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); 
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	static void Dijkstra(int start, int n, int m ) {
		pq.add(new Airport(start,n, m )); 
		
		
		while (!pq.isEmpty()) {
			Airport now = pq.poll(); 
			if (now.to == n) {
				break;
			}
			for(Airport air :airport[now.to]) {
				int nexttime = now.time + air.time; 
				int nextcost = now.cost + air.cost; 
				if (time[air.to] < nexttime) {
					continue; 
				}
				if (nextcost > m || cost[air.to] < nextcost)
				{
					continue; 
				}
				
				time[air.to]= nexttime; 
				cost[air.to] = nextcost; 
				pq.add(new Airport (air.to, nextcost, nexttime)); 
				
			}
		}
	}
}

	

[wjdgns7712]

단순 다익스트라만 이용해선 안되고 DP를 이용하셔야합니다!