On this page
Approach
Let best[v][c] be the minimum travel time to reach airport v with total cost at most c. Initialize every entry to infinity except best[0][c] = 0 for every budget c, since the start is reachable without spending any money. For each ticket, consider the new cost and relax only if it is within M. When a route improves a budget entry, propagate that time to larger budgets until an existing entry is already as good; more available budget cannot make the best time worse.
Run Dijkstra’s algorithm over these (airport, cost) states. The priority queue is ordered by travel time using Integer.compare, avoiding subtraction overflow. Skip a state if its time is greater than the best time for its budget; a cheaper route with less spending dominates it. Stop when the destination is popped: all ticket times are nonnegative, so this is the minimum travel time among all budget-feasible routes. Create the graph, table, and queue inside each test case so no state leaks between cases.
The invariant is that each finite entry is the best time found for its airport under that budget, and each queued state is a feasible route at its recorded cost. Relaxation checks every next ticket within the input budget; propagating improvements to larger budgets preserves the at-most-budget meaning. Since ticket times are nonnegative, Dijkstra’s minimum-time extraction finalizes feasible routes in order. Thus, the first non-stale destination state popped has minimum travel time among all budget-feasible routes.
There are at most N(M + 1) table states, so the table uses O(NM) space. With K ticket edges, sparse-state priority-queue work is approximately O(K log(NM)); in the worst case, tickets may be examined from many budget states, giving an explicit bound of O(KM log(NM)).
Java
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class Main {
private static class Ticket {
final int destination;
final int cost;
final int time;
Ticket(int destination, int cost, int time) {
this.destination = destination;
this.cost = cost;
this.time = time;
}
}
private static class State {
final int airport;
final int cost;
final int time;
State(int airport, int cost, int time) {
this.airport = airport;
this.cost = cost;
this.time = time;
}
}
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
int testCases = input.nextInt();
StringBuilder output = new StringBuilder();
for (int testCase = 0; testCase < testCases; testCase++) {
int airportCount = input.nextInt();
int budget = input.nextInt();
int ticketCount = input.nextInt();
List<Ticket>[] graph = new ArrayList[airportCount];
for (int airport = 0; airport < airportCount; airport++) {
graph[airport] = new ArrayList<>();
}
for (int i = 0; i < ticketCount; i++) {
int from = input.nextInt() - 1;
int to = input.nextInt() - 1;
int cost = input.nextInt();
int time = input.nextInt();
graph[from].add(new Ticket(to, cost, time));
}
int[][] best = new int[airportCount][budget + 1];
for (int[] times : best) {
Arrays.fill(times, Integer.MAX_VALUE);
}
for (int budgetLimit = 0; budgetLimit <= budget; budgetLimit++) {
best[0][budgetLimit] = 0;
}
PriorityQueue<State> queue = new PriorityQueue<>(
(left, right) -> Integer.compare(left.time, right.time));
queue.add(new State(0, 0, 0));
int answer = -1;
while (!queue.isEmpty()) {
State current = queue.poll();
if (current.time > best[current.airport][current.cost]) {
continue;
}
if (current.airport == airportCount - 1) {
answer = current.time;
break;
}
for (Ticket ticket : graph[current.airport]) {
int nextCost = current.cost + ticket.cost;
if (nextCost > budget) {
continue;
}
int nextTime = current.time + ticket.time;
if (nextTime < best[ticket.destination][nextCost]) {
for (int limit = nextCost; limit <= budget; limit++) {
if (nextTime >= best[ticket.destination][limit]) {
break;
}
best[ticket.destination][limit] = nextTime;
}
queue.add(new State(ticket.destination, nextCost, nextTime));
}
}
}
if (answer == -1) {
output.append("Poor KCM\n");
} else {
output.append(answer).append('\n');
}
}
System.out.print(output);
}
private static class FastScanner {
private final BufferedInputStream input = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int position;
private int length;
private int read() throws IOException {
if (position == length) {
length = input.read(buffer);
position = 0;
if (length == -1) {
return -1;
}
}
return buffer[position++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
}