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; }
choi2627 7년 전
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");
}
}
}
}