백준 10217번: KCM Travem - Java 다익스트라, DP

https://www.acmicpc.net/problem/10217

10217번: KCM Travel

 

일반적으로 최소비용만 고려하는 다익스트라와 달리

이 문제는 고려해야하는 변수가 최소시간과 함께 M 이하의 cost를 고려해야한다.

즉 변수가 두개이기 때문에

메모리를 더 사용하여 cost에 따른 최소시간을 저장해둘 필요가 있다.

그렇기에 dp가 필요하다.

 

 

 

import java.util.*;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;


class Edge implements Comparable<Edge>{
    int x,c,d;
    Edge(int x, int c, int d){
        this.x = x;
        this.c = c;
        this.d = d;
    }

    public int compareTo(Edge e){
        return d - e.d;
    }
}


public class Main {
    static ArrayList<Edge> adj[];
    static PriorityQueue<Edge> Q = new PriorityQueue<>();
    static int dp[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        String[] split;
        for (int T = 0; T < t; T++) {
            int n, m, k;
            split = br.readLine().split(" ");
            n = Integer.parseInt(split[0]);
            m = Integer.parseInt(split[1]);
            k = Integer.parseInt(split[2]);

            dp = new int[n+1][m+1];
            Q.clear();
            adj = new ArrayList[n+1];
            for(int i=1; i<=n; i++){
                adj[i] = new ArrayList<Edge>();
                Arrays.fill(dp[i], Integer.MAX_VALUE);
            }


            for(int i=0; i<k; i++){
                int a,b,c,d;
                split = br.readLine().split(" ");
                a = Integer.parseInt(split[0]);
                b = Integer.parseInt(split[1]);
                c = Integer.parseInt(split[2]);
                d = Integer.parseInt(split[3]);

                adj[a].add(new Edge(b,c,d));
            }

            Q.add(new Edge(1,0,0));


            int ans = Integer.MAX_VALUE;



            while(!Q.isEmpty()){
                Edge cur = Q.poll();

                if(cur.x == n) {
                    ans = cur.d;
                    break;
                }

                for(Edge nx : adj[cur.x]){
                    if(cur.c + nx.c > m) continue;
                    if(dp[nx.x][cur.c+nx.c] <= cur.d + nx.d) continue;
                    dp[nx.x][cur.c+nx.c] = cur.d + nx.d;
                    Q.add(new Edge(nx.x, cur.c + nx.c , cur.d + nx.d));
                }
            }
            

            if(ans!=Integer.MAX_VALUE){
                bw.write(Integer.toString(ans));
            }
            else bw.write("Poor KCM");
            bw.write("\n");

        }
        bw.flush();
    }
}