Saturday, August 29, 2026

import math
from typing import List

def findCheapestPrice_bellman(n: int, flights: List[List[int]], 
                               src: int, dst: int, k: int) -> int:
    # Initialize: infinite cost to all nodes except source
    # 初始化：除出发点外全部为无穷大
    dist = [math.inf] * n
    dist[src] = 0
    
    # Run K+1 iterations = at most K+1 flights = at most K stops
    # 跑 K+1 轮 = 最多 K+1 次航班 = 最多 K 次中转
    for i in range(k + 1):
        # CRITICAL: snapshot the current state before this round of relaxation
        # 关键：必须用上一轮的快照，防止在本轮内链式更新
        temp_dist = dist.copy()
        
        for u, v, price in flights:
            # Relax edge: can we reach v cheaper via u?
            # 松弛：能否通过 u 更便宜地到达 v？
            if dist[u] != math.inf and dist[u] + price < temp_dist[v]:
                temp_dist[v] = dist[u] + price
        
        dist = temp_dist  # commit this round's results
    
    return -1 if dist[dst] == math.inf else dist[dst]

import heapq
import collections

def findCheapestPrice_dijkstra(n: int, flights: List[List[int]], 
                                src: int, dst: int, k: int) -> int:
    # Build adjacency list: graph[u] = [(v, price), ...]
    # 构建邻接表
    graph = collections.defaultdict(list)
    for u, v, price in flights:
        graph[u].append((v, price))
    
    # Min-heap: (cost, node, stops_used)
    # 优先队列：（花费，节点，已用停站数）
    heap = [(0, src, 0)]
    
    # visited[node] = min stops used when we reached this node with some cost
    # We can revisit a node if we have fewer stops used
    # 已访问：记录到达该节点时用的最少停站数
    visited = {}
    
    while heap:
        cost, node, stops = heapq.heappop(heap)
        
        # If we've reached the destination, return immediately
        # (Dijkstra guarantee: first time we pop dst is cheapest)
        # 第一次弹出目的地即为最优解
        if node == dst:
            return cost
        
        # Pruning: if we've seen this node with fewer/equal stops, skip
        # 剪枝：如果曾以更少中转数到达此节点，跳过
        if node in visited and visited[node] <= stops:
            continue
        visited[node] = stops
        
        # Can't take more flights if we've used K+1 already
        # 已用 K 次中转（K+1 次航班），不能继续飞了
        if stops == k + 1:
            continue
        
        for neighbor, price in graph[node]:
            new_cost = cost + price
            heapq.heappush(heap, (new_cost, neighbor, stops + 1))
    
    return -1

反例说明：
假设我们有两条路径都到达节点2：
  路径A: cost=100, stops=0（但没有更多廉价边继续走）
  路径B: cost=150, stops=2（但从这里出发还剩K-2次中转可用）

如果仅靠 cost 决定 visited，路径A会阻止路径B被处理。
但路径B 可能因为"剩余中转次数更多"而到达目的地，路径A 却不行。

def findCheapestPrice_dp(n: int, flights: List[List[int]], 
                          src: int, dst: int, k: int) -> int:
    # dp[node] = cheapest cost to reach node using at most i flights so far
    # dp[节点] = 用恰好 i 次航班到达该节点的最小花费
    dp = [math.inf] * n
    dp[src] = 0
    
    # K stops = K+1 flights total
    for _ in range(k + 1):
        temp = dp.copy()  # snapshot: same "no chain update" rule
        for u, v, price in flights:
            if dp[u] != math.inf:
                temp[v] = min(temp[v], dp[u] + price)
        dp = temp
    
    return -1 if dp[dst] == math.inf else dp[dst]

# Note: BFS/DP and Bellman-Ford are mathematically identical here.
# The difference is purely in how you think about it:
# Bellman-Ford: "relax all edges K+1 times"
# BFS/DP: "compute optimal cost for exactly i flights, for i = 1..K+1"

import math
import heapq
import collections
from typing import List

def findCheapestPrice(n: int, flights: List[List[int]], 
                       src: int, dst: int, k: int) -> int:
    """
    Bellman-Ford approach — recommended for interviews.
    Time:  O(K * E) where E = number of flights
    Space: O(N) for distance array
    """
    dist = [math.inf] * n
    dist[src] = 0
    
    for _ in range(k + 1):
        temp = dist.copy()          # snapshot before this round
        for u, v, price in flights:
            if dist[u] != math.inf:
                temp[v] = min(temp[v], dist[u] + price)
        dist = temp
    
    return -1 if dist[dst] == math.inf else dist[dst]


# Test cases
def run_tests():
    test_cases = [
        # (n, flights, src, dst, k, expected)
        (3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 1, 200),
        (3, [[0,1,100],[1,2,100],[0,2,500]], 0, 2, 0, 500),
        (4, [[0,1,100],[1,2,100],[2,3,100],[0,3,1000]], 0, 3, 1, 1000),
        (4, [[0,1,100],[1,2,100],[2,3,100],[0,3,1000]], 0, 3, 2, 300),
        (2, [[1,0,5]], 0, 1, 1, -1),  # no path from src to dst
        (1, [], 0, 0, 0, 0),          # src == dst, cost = 0
    ]
    
    for i, (n, flights, src, dst, k, expected) in enumerate(test_cases):
        result = findCheapestPrice(n, flights, src, dst, k)
        status = "✅" if result == expected else "❌"
        print(f"Test {i+1}: {status} got={result}, expected={expected}")

run_tests()

Test 1: ✅ got=200, expected=200
Test 2: ✅ got=500, expected=500
Test 3: ✅ got=1000, expected=1000
Test 4: ✅ got=300, expected=300
Test 5: ✅ got=-1, expected=-1
Test 6: ✅ got=0, expected=0

# ❌ WRONG: single dist array — chain update within same round
dist = [0, inf, inf]
for u, v, price in flights:
    if dist[u] != inf:
        dist[v] = min(dist[v], dist[u] + price)
# In round 1: 0→1 updates dist[1]=100, then 1→2 IMMEDIATELY uses dist[1]=100
# This effectively uses 2 flights in 1 round — violates K constraint!

# ✅ CORRECT: use temp array (snapshot)
temp = dist.copy()
for u, v, price in flights:
    if dist[u] != inf:      # read from OLD dist
        temp[v] = min(temp[v], dist[u] + price)  # write to NEW temp
dist = temp

# If src == dst, cost is 0 — but the initial dist[src]=0 handles this.
# Your code should return 0 without any flights. ✅

# k=0: no stops allowed → only direct flights src→dst count
# Bellman-Ford handles this naturally: loop runs exactly once (k+1=1)

# Wrong: if node in visited: continue  (blocks valid paths with more stops remaining)
# Right: if node in visited and visited[node] <= stops: continue

# If dst is unreachable within K stops, dist[dst] stays inf → return -1
return -1 if dist[dst] == math.inf else dist[dst]

# Template: Cheapest Flights Within K Stops (Bellman-Ford)
def findCheapestPrice(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(k + 1):          # K+1 flights = K stops
        temp = dist.copy()           # snapshot! no chain updates
        for u, v, p in flights:
            if dist[u] != float('inf'):
                temp[v] = min(temp[v], dist[u] + p)
        dist = temp
    return -1 if dist[dst] == float('inf') else dist[dst]
# Time: O(K·E) | Space: O(N)