What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

10. K-Step Edge Relaxation: Cheapest Flights Within K Stops (LC 787) • Invariant Proof & Speed-Run

Theory Context•Graph Algorithms

MediumLC 787

Cheapest Flights Within K Stops (LeetCode 787)

Target Frequency:GoogleAppleNetflix

Picture an airline network over n cities, numbered 0 to n - 1. Each entry [from_i, to_i, price_i] of flights is a one-way flight: it leaves from_i, lands in to_i, and its ticket costs price_i.

You want to travel from city src to city dst and pay as little as possible in total, but you accept at most k stops: a stop is a city you land in on the way, other than src and dst, so the trip uses at most k + 1 flights. Return the lowest total ticket price of such a trip, or -1 when no trip with at most k stops gets you to dst.

Worked Examples

Example 1

Input:n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1

Output:700

Explanation: Flying 0 -> 1 -> 3 lands in one city on the way (1 stop) and costs 100 + 600 = 700. Going 0 -> 1 -> 2 -> 3 would cost only 400, but it lands in two cities on the way, one more than k = 1 allows.

Example 2

Input:n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1

Output:200

Explanation: Flying 0 -> 1 -> 2 stays within 1 stop and costs 100 + 100 = 200, beating the direct 500 flight.

Example 3

Input:n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0

Output:500

Explanation: With 0 stops allowed, only the direct flight 0 -> 2 qualifies, at a cost of 500.

⚖️Formal Constraints & Bounds

2 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= from_i, to_i < n
from_i != to_i
1 <= price_i <= 10⁴
There will not be any multiple flights between two cities
0 <= src, dst, k < n
src != dst

Deep-Dive & Conceptual Insights

Core Insight

Each of the k + 1 rounds reads last round's prices and writes into tmp_prices = prices.copy(), so a round adds exactly one flight and, after round i, prices[v] is the cheapest route to v with at most i flights.

Real-World Scenario & Production Applications

Multi-leg airline routing with strict stop limits, bounded transit budgets, and step-constrained network packet delivery.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: One Round per Allowed Flight

At most k stops means at most k + 1 flights, so run exactly k + 1 rounds, starting from prices[src] = 0 and inf everywhere else.

Mathematical Recurrence / Code Invariant

prices = [float("inf")] * n
prices[src] = 0
for _ in range(k + 1):

Step-by-Step Execution Trace Table

Round	Flight `(u, v, price)`	`prices[u]` (last round)	Relaxation	`tmp_prices` after it
Start	-	-	`prices[src = 0] = 0`, all others $\infty$	`prices = [0, inf, inf, inf]`
Round 1 (up to 1 flight)	`(0, 1, 100)`	`0`	$0 + 100 < \infty \implies$ `tmp_prices[1] = 100`	`[0, 100, inf, inf]`
Round 1	`(1, 2, 100)`	`inf`	Skip: `tmp_prices[1]` is already 100, but the round reads `prices[1]`, so 0 -> 1 -> 2 must wait	`[0, 100, inf, inf]`
Round 1	`(2, 0, 100)`, `(1, 3, 600)`, `(2, 3, 200)`	`inf`	Skip	`[0, 100, inf, inf]`
Round 1 ends	-	-	`prices = tmp_prices`	`prices = [0, 100, inf, inf]`
Round 2 (up to 2 flights)	`(1, 2, 100)`	`100`	$100 + 100 < \infty \implies$ `tmp_prices[2] = 200`	`[0, 100, 200, inf]`
Round 2	`(1, 3, 600)`	`100`	$100 + 600 < \infty \implies$ `tmp_prices[3] = 700`	`[0, 100, 200, 700]`
Round 2	`(2, 3, 200)`	`inf`	Skip: 0 -> 1 -> 2 -> 3 would need a third flight	`[0, 100, 200, 700]`
End ( $k + 1 = 2$ rounds)	-	-	return `prices[3]`	`700`

Trace Inputn = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1

Expected700

Round	Flight `(u, v, price)`	`prices[u]` (last round)	Relaxation	`tmp_prices` after it
Start	-	-	`prices[src = 0] = 0`, all others $\infty$	`prices = [0, inf, inf, inf]`
Round 1 (up to 1 flight)	`(0, 1, 100)`	`0`	$0 + 100 < \infty \implies$ `tmp_prices[1] = 100`	`[0, 100, inf, inf]`
Round 1	`(1, 2, 100)`	`inf`	Skip: `tmp_prices[1]` is already 100, but the round reads `prices[1]`, so 0 -> 1 -> 2 must wait	`[0, 100, inf, inf]`
Round 1	`(2, 0, 100)`, `(1, 3, 600)`, `(2, 3, 200)`	`inf`	Skip	`[0, 100, inf, inf]`
Round 1 ends	-	-	`prices = tmp_prices`	`prices = [0, 100, inf, inf]`
Round 2 (up to 2 flights)	`(1, 2, 100)`	`100`	$100 + 100 < \infty \implies$ `tmp_prices[2] = 200`	`[0, 100, 200, inf]`
Round 2	`(1, 3, 600)`	`100`	$100 + 600 < \infty \implies$ `tmp_prices[3] = 700`	`[0, 100, 200, 700]`
Round 2	`(2, 3, 200)`	`inf`	Skip: 0 -> 1 -> 2 -> 3 would need a third flight	`[0, 100, 200, 700]`
End ( $k + 1 = 2$ rounds)	-	-	return `prices[3]`	`700`

Code Shape

Archetype Code Shape

Python

1	prices = [inf] * n
2	prices[src] = 0
3	for _ in range(k + 1):
4	tmp_prices = prices.copy()
5	for u, v, price in flights:
6	if prices[u] + price < tmp_prices[v]:
7	tmp_prices[v] = prices[u] + price
8	prices = tmp_prices
9	return prices[dst] if prices[dst] != inf else -1

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

Standard shortest-path algorithms find the cheapest path no matter how many edges it uses. When the path may use at most $K$ stops ( $K + 1$ flights), Dijkstra fails: it settles a city by its cheapest route, even when that route has too many stops, and never looks at the dearer route with fewer stops. Bellman-Ford fixes this by running exactly $K + 1$ rounds of relaxation over every flight, each round reading last round's prices and writing into a copy, tmp_prices, so that each round adds at most one flight.

✈️ The Analogy: A Flight Pass with Exactly K Layovers

Imagine an airline flight coupon that lets you book at most $K$ layovers (meaning at most $K + 1$ total flight legs). On Day 1, you can only look at direct 1-leg flights from your origin. On Day 2, you look at all flights reachable by taking 1 flight from any city you could already reach on Day 1. By freezing your prices table at the start of each round (tmp_prices = prices.copy()), you prevent "chaining" multiple flights in a single round — guaranteeing that after $K + 1$ rounds, you have explored every possible valid flight itinerary with at most $K$ stops.

🔑 The Key Idea in the Code

The copy tmp_prices = prices.copy() is the linchpin: every flight reads prices[u], last round's price, and writes tmp_prices[v]. Without the copy, updating prices[v] in place would let a later flight v -> w in the same round use that new price at once, so a single round could chain 2, 3 or more flights. With it, a round adds strictly one flight.

Writing into prices in place instead of a copy
Running range(k) rounds instead of range(k + 1)
Returning prices[dst] when it is still float("inf")
Dropping the prices[u] == INT_MAX check in Java or C++

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

The trip must cost as little as possible "in total" but may use "at most k stops", which means it "uses at most k + 1 flights": a cheapest path with a cap on the number of edges. Dijkstra's settled-means-final rule ignores the cap, so this is Bellman-Ford with k + 1 rounds.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

After round i, prices[v] is the cheapest route from src to v with at most i flights. Each round reads only prices, writes into tmp_prices = prices.copy(), relaxes a flight when prices[u] + price < tmp_prices[v], and ends with prices = tmp_prices.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

tmp_prices = prices.copy(): relaxing straight into prices lets one round chain several flights; on Example 1 the two-stop route 0 -> 1 -> 2 -> 3 (400) would beat the one-stop answer 700.
for _ in range(k + 1): k stops is k + 1 flights, so range(k) stops one flight short.
return prices[dst] if prices[dst] != float("inf") else -1: when no route with at most k stops reaches dst, the answer is -1, not infinity.
Plain Dijkstra on price alone settles a city by its cheapest route even when that route has too many stops, and never looks at it again: the cap needs the rounds (or the stop count in the heap state).

The 60-Second Interview Pitch

Say this out loud before you type a single line

This is Bellman-Ford with a cap on flights. At most k stops means at most k plus one flights, so I run exactly k plus one rounds, and each round lets every route grow by one flight. I keep prices, the cheapest known price per city, with the source at zero. Each round I copy prices into tmp prices, and for every flight from u to v, if u is reached and prices of u plus the ticket beats tmp prices of v, I write the new price into the copy. Then I publish the copy. After round i, prices holds the cheapest route of at most i flights, because any such route is a shorter route plus one last flight, and the round tries every last flight. The trap is updating in place: one round would chain several flights, and a cheap route with too many stops would win. It's O(K times (V plus E)) time and O(V) space.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(K · (V + E))

Look at the code: for _ in range(k + 1) runs K + 1 rounds. Each round does tmp_prices = prices.copy(), which is O(V), then for u, v, price in flights tries each of the E flights once with O(1) work: the infinity test, the comparison and at most one write. One round is O(V + E), so the run is (K + 1) · (V + E) = O(K · (V + E)). On a dense network (E close to V²) the flights dominate; on a sparse one the copies do, which is why V stays in the bound.

SPACE COMPLEXITY

O(V)

prices and tmp_prices hold V entries each; after prices = tmp_prices the old array is freed, so at most two arrays live at once. There is no recursion and no heap. The input flights is not counted.

Formal Recurrence Relation

T(K, V, E) = (K + 1) · (V + E) = O(K · (V + E))

Derivation Progression

Rounds

for _ in range(k + 1): K + 1 iterations

One round per allowed flight: k stops means at most k + 1 flights.

Copy per round

tmp_prices = prices.copy(): O(V)

Each round starts by copying the V prices, so writes never touch the array being read.

Relax every flight once per round

sum over flights of O(1) = O(E)

Each flight costs one infinity test, one comparison and at most one write into tmp_prices.

Total

(K + 1) · (O(V) + O(E)) = O(K · (V + E))

The rounds multiply the per-round cost of one copy plus one pass over the flights.

Variable Definitions

$K$

The stop limit k; the loop runs K + 1 rounds, one per allowed flight

$E$

Number of flights, len(flights)

$V$

Number of cities, n

Memory Architecture & Bounds

🟣 Call Stack

O(1): iterative, no recursion

🔵 Auxiliary Heap

O(V): prices and tmp_prices, V entries each, at most two at a time

🟢 Output Space

O(1): one integer

Boundary Best / Worst Cases

Best Case

$O(K · (V + E))$ : every round tries every flight, even after the prices stop changing.

Average Case

$O(K · (V + E))$ .

Worst Case

$O(K · (V + E))$ : the same work on every input of that size.

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Scale signal: each round is one pass over the flights, so the whole run is $(k + 1) \cdot (V + E) \le 100 \cdot 5050 \approx 5 \times 10^5$ steps, while listing every route of up to $k + 1$ flights grows like $V^{k+1}$ .

CONSTRAINTS & BOUNDS

$n \le 100$ cities, at most $n(n-1)/2 = 4950$ flights, $k < n$ . Budget: $(k + 1) \cdot (V + E) \le 100 \cdot 5050 \approx 5 \times 10^5$ steps, and two arrays of $n$ prices.

FAANG PRODUCTION TRAPS & EDGE CASES

A round that changes no price means later rounds can't change any either, so a production version stops early there. Without a cap, $V - 1$ rounds suffice, and a round after that which still lowers a price means a negative cycle.

Core Algorithmic State Invariants

Example 2: The Second Round Finds the Cheaper Route

Round 1 gives prices = [0, 100, 500]: only direct flights count. Round 2 tries 0 -> 1 -> 2 for 100 + 100 = 200 < 500, so with k = 1 the answer is 200.

Example 3: k = 0 Is One Round

Only round 1 runs, and prices[2] = 500 from the direct flight. The 200 route needs a second flight, which k = 0 does not allow, so the answer is 500.

Example 1 With k = 2

A third round makes 0 -> 1 -> 2 -> 3 legal, and prices[3] drops from 700 to 400. The graph is the same; the cap alone decides which routes count.

Theory Context•Graph Algorithms

MediumLC 787

Cheapest Flights Within K Stops (LeetCode 787)

Target Frequency:GoogleAppleNetflix

Worked Examples

Example 1

Input:n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1

Output:700

Example 2

Input:n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1

Output:200

Explanation: Flying 0 -> 1 -> 2 stays within 1 stop and costs 100 + 100 = 200, beating the direct 500 flight.

Example 3

Input:n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0

Output:500

Explanation: With 0 stops allowed, only the direct flight 0 -> 2 qualifies, at a cost of 500.

⚖️Formal Constraints & Bounds

2 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= from_i, to_i < n
from_i != to_i
1 <= price_i <= 10⁴
There will not be any multiple flights between two cities
0 <= src, dst, k < n
src != dst

Deep-Dive & Conceptual Insights

Core Insight

Real-World Scenario & Production Applications

Multi-leg airline routing with strict stop limits, bounded transit budgets, and step-constrained network packet delivery.

Subproblems & Recurrence Decomposition3 Phases

🧩Subproblem 1: One Round per Allowed Flight

At most k stops means at most k + 1 flights, so run exactly k + 1 rounds, starting from prices[src] = 0 and inf everywhere else.

Mathematical Recurrence / Code Invariant

prices = [float("inf")] * n
prices[src] = 0
for _ in range(k + 1):

Step-by-Step Execution Trace Table

Round	Flight `(u, v, price)`	`prices[u]` (last round)	Relaxation	`tmp_prices` after it
Start	-	-	`prices[src = 0] = 0`, all others $\infty$	`prices = [0, inf, inf, inf]`
Round 1 (up to 1 flight)	`(0, 1, 100)`	`0`	$0 + 100 < \infty \implies$ `tmp_prices[1] = 100`	`[0, 100, inf, inf]`
Round 1	`(1, 2, 100)`	`inf`	Skip: `tmp_prices[1]` is already 100, but the round reads `prices[1]`, so 0 -> 1 -> 2 must wait	`[0, 100, inf, inf]`
Round 1	`(2, 0, 100)`, `(1, 3, 600)`, `(2, 3, 200)`	`inf`	Skip	`[0, 100, inf, inf]`
Round 1 ends	-	-	`prices = tmp_prices`	`prices = [0, 100, inf, inf]`
Round 2 (up to 2 flights)	`(1, 2, 100)`	`100`	$100 + 100 < \infty \implies$ `tmp_prices[2] = 200`	`[0, 100, 200, inf]`
Round 2	`(1, 3, 600)`	`100`	$100 + 600 < \infty \implies$ `tmp_prices[3] = 700`	`[0, 100, 200, 700]`
Round 2	`(2, 3, 200)`	`inf`	Skip: 0 -> 1 -> 2 -> 3 would need a third flight	`[0, 100, 200, 700]`
End ( $k + 1 = 2$ rounds)	-	-	return `prices[3]`	`700`

Trace Inputn = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1

Expected700

Round	Flight `(u, v, price)`	`prices[u]` (last round)	Relaxation	`tmp_prices` after it
Start	-	-	`prices[src = 0] = 0`, all others $\infty$	`prices = [0, inf, inf, inf]`
Round 1 (up to 1 flight)	`(0, 1, 100)`	`0`	$0 + 100 < \infty \implies$ `tmp_prices[1] = 100`	`[0, 100, inf, inf]`
Round 1	`(1, 2, 100)`	`inf`	Skip: `tmp_prices[1]` is already 100, but the round reads `prices[1]`, so 0 -> 1 -> 2 must wait	`[0, 100, inf, inf]`
Round 1	`(2, 0, 100)`, `(1, 3, 600)`, `(2, 3, 200)`	`inf`	Skip	`[0, 100, inf, inf]`
Round 1 ends	-	-	`prices = tmp_prices`	`prices = [0, 100, inf, inf]`
Round 2 (up to 2 flights)	`(1, 2, 100)`	`100`	$100 + 100 < \infty \implies$ `tmp_prices[2] = 200`	`[0, 100, 200, inf]`
Round 2	`(1, 3, 600)`	`100`	$100 + 600 < \infty \implies$ `tmp_prices[3] = 700`	`[0, 100, 200, 700]`
Round 2	`(2, 3, 200)`	`inf`	Skip: 0 -> 1 -> 2 -> 3 would need a third flight	`[0, 100, 200, 700]`
End ( $k + 1 = 2$ rounds)	-	-	return `prices[3]`	`700`

Code Shape

Archetype Code Shape

Python

1	prices = [inf] * n
2	prices[src] = 0
3	for _ in range(k + 1):
4	tmp_prices = prices.copy()
5	for u, v, price in flights:
6	if prices[u] + price < tmp_prices[v]:
7	tmp_prices[v] = prices[u] + price
8	prices = tmp_prices
9	return prices[dst] if prices[dst] != inf else -1

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

✈️ The Analogy: A Flight Pass with Exactly K Layovers

🔑 The Key Idea in the Code

Writing into prices in place instead of a copy
Running range(k) rounds instead of range(k + 1)
Returning prices[dst] when it is still float("inf")
Dropping the prices[u] == INT_MAX check in Java or C++

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

tmp_prices = prices.copy(): relaxing straight into prices lets one round chain several flights; on Example 1 the two-stop route 0 -> 1 -> 2 -> 3 (400) would beat the one-stop answer 700.
for _ in range(k + 1): k stops is k + 1 flights, so range(k) stops one flight short.
return prices[dst] if prices[dst] != float("inf") else -1: when no route with at most k stops reaches dst, the answer is -1, not infinity.
Plain Dijkstra on price alone settles a city by its cheapest route even when that route has too many stops, and never looks at it again: the cap needs the rounds (or the stop count in the heap state).

The 60-Second Interview Pitch

Say this out loud before you type a single line

This is Bellman-Ford with a cap on flights. At most k stops means at most k plus one flights, so I run exactly k plus one rounds, and each round lets every route grow by one flight. I keep prices, the cheapest known price per city, with the source at zero. Each round I copy prices into tmp prices, and for every flight from u to v, if u is reached and prices of u plus the ticket beats tmp prices of v, I write the new price into the copy. Then I publish the copy. After round i, prices holds the cheapest route of at most i flights, because any such route is a shorter route plus one last flight, and the round tries every last flight. The trap is updating in place: one round would chain several flights, and a cheap route with too many stops would win. It's O(K times (V plus E)) time and O(V) space.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(K · (V + E))

SPACE COMPLEXITY

O(V)

Formal Recurrence Relation

T(K, V, E) = (K + 1) · (V + E) = O(K · (V + E))

Derivation Progression

Rounds

for _ in range(k + 1): K + 1 iterations

One round per allowed flight: k stops means at most k + 1 flights.

Copy per round

tmp_prices = prices.copy(): O(V)

Each round starts by copying the V prices, so writes never touch the array being read.

Relax every flight once per round

sum over flights of O(1) = O(E)

Each flight costs one infinity test, one comparison and at most one write into tmp_prices.

Total

(K + 1) · (O(V) + O(E)) = O(K · (V + E))

The rounds multiply the per-round cost of one copy plus one pass over the flights.

Variable Definitions

$K$

The stop limit k; the loop runs K + 1 rounds, one per allowed flight

$E$

Number of flights, len(flights)

$V$

Number of cities, n

Memory Architecture & Bounds

🟣 Call Stack

O(1): iterative, no recursion

🔵 Auxiliary Heap

O(V): prices and tmp_prices, V entries each, at most two at a time

🟢 Output Space

O(1): one integer

Boundary Best / Worst Cases

Best Case

$O(K · (V + E))$ : every round tries every flight, even after the prices stop changing.

Average Case

$O(K · (V + E))$ .

Worst Case

$O(K · (V + E))$ : the same work on every input of that size.

Graph & Tree Traversal Frontier

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

$n \le 100$ cities, at most $n(n-1)/2 = 4950$ flights, $k < n$ . Budget: $(k + 1) \cdot (V + E) \le 100 \cdot 5050 \approx 5 \times 10^5$ steps, and two arrays of $n$ prices.

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

Example 2: The Second Round Finds the Cheaper Route

Round 1 gives prices = [0, 100, 500]: only direct flights count. Round 2 tries 0 -> 1 -> 2 for 100 + 100 = 200 < 500, so with k = 1 the answer is 200.

Example 3: k = 0 Is One Round

Only round 1 runs, and prices[2] = 500 from the direct flight. The 200 route needs a second flight, which k = 0 does not allow, so the answer is 500.

Example 1 With k = 2

A third round makes 0 -> 1 -> 2 -> 3 legal, and prices[3] drops from 700 to 400. The graph is the same; the cap alone decides which routes count.

Round

Flight (u, v, price)

prices[u] (last round)

Relaxation

tmp_prices after it

Start

prices[src = 0] = 0, all others

\infty

prices = [0, inf, inf, inf]

Round 1 (up to 1 flight)

(0, 1, 100)

0

0 + 100 < \infty \implies

tmp_prices[1] = 100

[0, 100, inf, inf]

Round 1

(1, 2, 100)

inf

Skip: tmp_prices[1] is already 100, but the round reads prices[1], so 0 -> 1 -> 2 must wait

[0, 100, inf, inf]

Round 1

(2, 0, 100), (1, 3, 600), (2, 3, 200)

inf

Skip

[0, 100, inf, inf]

Round 1 ends

prices = tmp_prices

prices = [0, 100, inf, inf]

Round 2 (up to 2 flights)

(1, 2, 100)

100

100 + 100 < \infty \implies

tmp_prices[2] = 200

[0, 100, 200, inf]

Round 2

(1, 3, 600)

100

100 + 600 < \infty \implies

tmp_prices[3] = 700

[0, 100, 200, 700]

Round 2

(2, 3, 200)

inf

Skip: 0 -> 1 -> 2 -> 3 would need a third flight

[0, 100, 200, 700]

End (

k + 1 = 2

rounds)

return prices[3]

700

Round

Flight (u, v, price)

prices[u] (last round)

Relaxation

tmp_prices after it

Start

prices[src = 0] = 0, all others

\infty

prices = [0, inf, inf, inf]

Round 1 (up to 1 flight)

(0, 1, 100)

0

0 + 100 < \infty \implies

tmp_prices[1] = 100

[0, 100, inf, inf]

Round 1

(1, 2, 100)

inf

Skip: tmp_prices[1] is already 100, but the round reads prices[1], so 0 -> 1 -> 2 must wait

[0, 100, inf, inf]

Round 1

(2, 0, 100), (1, 3, 600), (2, 3, 200)

inf

Skip

[0, 100, inf, inf]

Round 1 ends

prices = tmp_prices

prices = [0, 100, inf, inf]

Round 2 (up to 2 flights)

(1, 2, 100)

100

100 + 100 < \infty \implies

tmp_prices[2] = 200

[0, 100, 200, inf]

Round 2

(1, 3, 600)

100

100 + 600 < \infty \implies

tmp_prices[3] = 700

[0, 100, 200, 700]

Round 2

(2, 3, 200)

inf

Skip: 0 -> 1 -> 2 -> 3 would need a third flight

[0, 100, 200, 700]

End (

k + 1 = 2

rounds)

return prices[3]

700

🧭 Conceptual Foundation & Pattern Intuition

✈️ The Analogy: A Flight Pass with Exactly K Layovers

🔑 The Key Idea in the Code

Round

Flight (u, v, price)

prices[u] (last round)

Relaxation

tmp_prices after it

Start

prices[src = 0] = 0, all others

\infty

prices = [0, inf, inf, inf]

Round 1 (up to 1 flight)

(0, 1, 100)

0

0 + 100 < \infty \implies

tmp_prices[1] = 100

[0, 100, inf, inf]

Round 1

(1, 2, 100)

inf

Skip: tmp_prices[1] is already 100, but the round reads prices[1], so 0 -> 1 -> 2 must wait

[0, 100, inf, inf]

Round 1

(2, 0, 100), (1, 3, 600), (2, 3, 200)

inf

Skip

[0, 100, inf, inf]

Round 1 ends

prices = tmp_prices

prices = [0, 100, inf, inf]

Round 2 (up to 2 flights)

(1, 2, 100)

100

100 + 100 < \infty \implies

tmp_prices[2] = 200

[0, 100, 200, inf]

Round 2

(1, 3, 600)

100

100 + 600 < \infty \implies

tmp_prices[3] = 700

[0, 100, 200, 700]

Round 2

(2, 3, 200)

inf

Skip: 0 -> 1 -> 2 -> 3 would need a third flight

[0, 100, 200, 700]

End (

k + 1 = 2

rounds)

return prices[3]

700

Round

Flight (u, v, price)

prices[u] (last round)

Relaxation

tmp_prices after it

Start

prices[src = 0] = 0, all others

\infty

prices = [0, inf, inf, inf]

Round 1 (up to 1 flight)

(0, 1, 100)

0

0 + 100 < \infty \implies

tmp_prices[1] = 100

[0, 100, inf, inf]

Round 1

(1, 2, 100)

inf

Skip: tmp_prices[1] is already 100, but the round reads prices[1], so 0 -> 1 -> 2 must wait

[0, 100, inf, inf]

Round 1

(2, 0, 100), (1, 3, 600), (2, 3, 200)

inf

Skip

[0, 100, inf, inf]

Round 1 ends

prices = tmp_prices

prices = [0, 100, inf, inf]

Round 2 (up to 2 flights)

(1, 2, 100)

100

100 + 100 < \infty \implies

tmp_prices[2] = 200

[0, 100, 200, inf]

Round 2

(1, 3, 600)

100

100 + 600 < \infty \implies

tmp_prices[3] = 700

[0, 100, 200, 700]

Round 2

(2, 3, 200)

inf

Skip: 0 -> 1 -> 2 -> 3 would need a third flight

[0, 100, 200, 700]

End (

k + 1 = 2

rounds)

return prices[3]

700