[백준 10217 : JAVA] KCM Travel / 벨만-포드

개요

 

문제를 읽어보면 최단 시간을 구하는 문제이면서 동시에 티켓 가격은 조건을 만족해야 한다.

 

가중치가 1이 아니므로 DFS, BFS가 아닌 다익스트라, 벨만 포드, 플로이드 와샬을 사용해야 한다.

 

한 노드 ▶ 노드 이므로 다익스트라, 벨만 포드를 사용해야 한다.

 

음의 가중치는 없기 때문에 다익스트라를 사용해야 한다.

 

결국 다익스트라를 사용해야 하는데 이 문제는 다익스트라 + dp를 이용해서 풀이한다.

이때 dp[i][j] = k가 있다면, i노드까지 j비용으로 갈 수 있는 최소의 시간 = k 라고 생각하고 풀이에 들어간다.

 

 

문제

 

각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다.

초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 비용만을 여행비로써 부담해주겠다고 한다. 인천에서 LA행 직항 한 번 끊어주는게 그렇게 힘드냐고 따지고도 싶었지만, 다가올 결승 대회를 생각하면 대회 외적인 곳에 마음을 쓰고 싶지 않은 것 또한 사실이었다. 그래서 찬민은 인천에서 LA까지 M원 이하로 사용하면서 도착할 수 있는 가장 빠른 길을 차선책으로 택하기로 하였다.

각 공항들간 티켓가격과 이동시간이 주어질 때, 찬민이 인천에서 LA로 갈 수 있는 가장 빠른 길을 찾아 찬민의 대회 참가를 도와주자.

 

입력

 

풀이

 

시간을 기준으로 우선순위큐에 집어넣어 계산한다.

 

코드

 

import java.io.*;
import java.util.*;

public class Main{
    static class AirPlane implements Comparable<AirPlane>{
        int end;
        int cost;
        int time;

        public AirPlane(int end, int cost, int time){
            this.end = end;
            this.cost = cost;
            this.time = time;
        }

        @Override
        public int compareTo(AirPlane airPlane) {
            if(this.time == airPlane.time) return cost - airPlane.cost;
            return this.time - airPlane.time;
        }
    }

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static final int INF = 100 * 1_000;
    static int n, m, k;
    static List<AirPlane> list[];
    static int dp[][];

    public static void main(String[] args) throws IOException {
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int i = 0 ; i < t; i++){
            init();
            int result = dijkstra();
            sb.append(result == INF ? "Poor KCM\n" : result + "\n");
        }

        bw.write(sb.toString());
        bw.close();
        br.close();
    }

    private static int dijkstra() {
        for(int i = 1 ; i < dp.length; i++)
            Arrays.fill(dp[i], INF);


       PriorityQueue<AirPlane> queue = new PriorityQueue<>();
       queue.add(new AirPlane(1, 0, 0));
       // 1번 노드까지 가는데 0 비용으로 갔을 때의 최소 시간
       dp[1][0] = 0;

       while(!queue.isEmpty()){
           AirPlane airPlane = queue.poll();
           int node = airPlane.end;
           int cost = airPlane.cost;
           int time = airPlane.time;

           if(node == n) break;
           if(dp[node][cost] < time) continue;
           dp[node][cost] = time;

           for(int i = 0 ; i < list[node].size(); i++){
               AirPlane toAirplane = list[node].get(i);
               int toNode = toAirplane.end;
               int toCost = cost + toAirplane.cost;
               int toTime = time + toAirplane.time;

               if(toCost > m) continue;
               if(dp[toNode][toCost] > toTime){
               	   // 불필요한 push를 막기위해서
                   // 다음과 같이 값을 설정해준다.
                   for(int j = toCost; j <= m; j++){
                       if(dp[toNode][j] > toTime) dp[toNode][j] = toTime;
                   }
                   queue.add(new AirPlane(toNode, toCost, toTime));
               }
           }
       }

       int result = Integer.MAX_VALUE;

       for(int i = 1; i <= m; i++)
           result = Math.min(result, dp[n][i]);


       return result;
    }

    private static void init() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        dp = new int[n + 1][m + 1];
        list = new ArrayList[n + 1];

        for(int i = 0 ; i <= n; i++)
            Arrays.fill(dp[i], INF);

        for(int i = 0; i <= n; i++)
            list[i] = new ArrayList<>();

        for(int i = 0 ; i < k; i++){
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());

            list[start].add(new AirPlane(end, cost, time));
        }
    }
}