choi2627   4년 전

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

class Edge implements Comparable<Edge>{
    int to, cost;
    int money;
    Edge(int to, int money, int cost) {
        this.to = to;
        this.money = money;
        this.cost = cost;

    }

    public int compareTo(Edge that) {
        if (this.cost < that.cost) {
            return -1;
        } else if (this.cost == that.cost) {
            if (this.to < that.to) return -1;
            else if (this.to > that.to) return 1;
            else return 0;
        } else {
            return 1;
        }
    }

}

public class Main {
    public static final int inf = 1000000000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        while(t-- > 0) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int k = sc.nextInt();

            List<Edge> a[] = (List<Edge>[]) new List[n+1];

            for(int i = 1; i <= n; i++) {
                a[i]= new ArrayList<Edge>();
            }

            for(int i = 0; i < k; i++) {
                int from = sc.nextInt();
                int to = sc.nextInt();
                int money = sc.nextInt();
                int cost = sc.nextInt();
                a[from].add(new Edge(to, money, cost));
            }

            int dist[] = new int[n+1];
            boolean check[] = new boolean[n+1];
            int money[] = new int[n+1];

            PriorityQueue<Edge> q = new PriorityQueue<>();

            for(int i = 1; i <= n; i++) {
                dist[i] = inf;
                check[i] = false;
                money[i] = 0;
            }

            dist[1] = 0;
            money[1] = 0;

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

            while(!q.isEmpty()){
                int x = q.remove().to;
                if(check[x]) continue;
                check[x] = true;
                for(Edge y : a[x]) {
                    if(money[y.to] <= m && dist[y.to] > dist[x] + y.cost){
                        dist[y.to] = dist[x] + y.cost;
                        money[y.to] = money[x] + y.money;
                        q.add(new Edge(y.to, money[y.to], dist[y.to]));
                    }
                }
            }

            if(money[n] <= m){
                if(dist[n] == inf) {
                    System.out.println("Poor KCM");
                } else {
                    System.out.println(dist[n]);
                }
            } else {
                System.out.println("Poor KCM");
            }

        }
    }
}

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