Cheapest Flights Within K Stops
Hay n ciudades, numeradas del 0 al n-1, y una lista de vuelos de ida: flights[i] = [from, to, price] es un vuelo desde la ciudad from hasta la ciudad to que cuesta price.
Devuelve el precio total más bajo de un viaje desde src hasta dst que haga como máximo k escalas, es decir, como máximo k+1 vuelos. Si no existe tal viaje, devuelve -1.
Función
- ninteger
- el número de ciudades
- flightsinteger-2d-array
- los vuelos de solo ida, cada uno como [from, to, price]
- srcinteger
- la ciudad donde comienza el viaje
- dstinteger
- la ciudad donde termina el viaje
- kinteger
- la mayor cantidad de paradas permitida entre src y dst
- Devuelveinteger
- el precio más bajo de un viaje con como máximo k paradas, o -1
Restricciones
2 ≤ n ≤ 10001 ≤ flights.length ≤ 4500flights[i] = [from, to, price]con0 ≤ from, to < nyfrom ≠ to1 ≤ price ≤ 104- No hay dos vuelos que compartan tanto
fromcomoto. 0 ≤ src, dst < nysrc ≠ dst0 ≤ k < n
Ejemplos
- Entrada
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 1
- Salida
- 230
- Explicación
- Una escala permite dos vuelos:
0 → 1 → 3cuesta 50 + 180 = 230 y0 → 2 → 3cuesta 200 + 50 = 250. La opción más barata,0 → 1 → 2 → 3, hace dos escalas.
- Entrada
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 2
- Salida
- 150
- Explicación
- Dos escalas permiten tres vuelos, así que ahora se permite
0 → 1 → 2 → 3, y cuesta 50 + 50 + 50 = 150.
- Entrada
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 0
- Salida
- -1
- Explicación
- Sin paradas, el viaje tendría que ser un vuelo directo de 0 a 3, y no hay ninguno.
Para ir más allá
¿Cómo devolverías las ciudades del viaje más barato, así como su precio?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
El viaje más barato en general puede tener demasiadas escalas, así que la ruta más corta sin más no es suficiente. Un precio solo es útil junto con el número de vuelos que se necesitaron.
Sea
cost[c]el precio más barato para llegar a la ciudadccon como máximorvuelos. Una pasada por cada vuelo lo convierte en el precio más barato con como máximor+1vuelos. Necesitask+1pasadas de este tipo.En cada pasada, lee los precios de la pasada anterior y escribe en una copia. Si actualizas en el mismo lugar, un vuelo puede basarse en un precio establecido en la misma pasada, y una pasada incluye dos vuelos sin que te des cuenta.
Solución
Este es un problema de camino más corto con un límite en el número de vuelos. El algoritmo de Dijkstra aplicado solo a las ciudades falla, porque la forma más barata de llegar a una ciudad puede consumir escalas que se necesitan para el resto del viaje. Bellman-Ford se ajusta al límite: la ronda r encuentra el precio más barato con como máximo r vuelos, así que ejecutas k+1 rondas.
Prueba todas las rutas con como máximo k+1 vuelos
Correcto, pero no termina con las pruebas más grandes
Intuición
Recorre cada ruta desde src con una pila de (ciudad, precio, vuelos usados). Una ruta que llega a dst registra su precio y termina, ya que todos los precios son positivos. Una ruta con k+1 vuelos se descarta; cualquier otra se amplía con cada vuelo que sale de su ciudad. Se construyen todos los viajes permitidos, así que el mejor precio registrado es correcto.
Las rutas crecen como d elevado a k+1, para d vuelos que salen de una ciudad. Con 4 vuelos por ciudad y k = 29, eso equivale a 4^30 ≈ 1.2 × 10^18 rutas.
Algoritmo
- Agrupa los vuelos por ciudad de salida.
- Apila
(src, 0, 0): ciudad, precio hasta el momento, vuelos realizados. - Desapila una ruta. Si su ciudad es
dst, conserva su precio si es el mejor hasta el momento. - De lo contrario, si ha realizado menos de
k+1vuelos, apila una ruta más larga por cada vuelo que salga de su ciudad. - Cuando la pila esté vacía, devuelve el mejor precio, o -1 si ninguna ruta llegó a
dst.
def findCheapestPrice(n, flights, src, dst, k):
out = [[] for _ in range(n)]
for a, b, price in flights:
out[a].append((b, price))
best = -1
# Each entry is a route in progress: (city, price so far, flights taken).
stack = [(src, 0, 0)]
while stack:
city, cost, used = stack.pop()
if city == dst:
if best == -1 or cost < best:
best = cost
continue
# k stops allow at most k+1 flights.
if used == k + 1:
continue
for nxt, price in out[city]:
stack.append((nxt, cost + price, used + 1))
return bestBellman-Ford limitado a k+1 rondas
Intuición
Sea cost[c] el precio más barato para llegar a la ciudad c con como máximo r vuelos. Con r = 0, solo se puede llegar a src, con un precio de 0. Un viaje a a con como máximo r vuelos, seguido de un vuelo a → b, es un viaje a b con como máximo r+1, así que cada ronda ofrece cost[a] + price a b por cada vuelo. Después de k+1 rondas, cost[dst] es la respuesta.
Cada ronda lee los precios de la ronda anterior y escribe en una copia, así que un precio establecido durante una ronda no puede servir para tomar otro vuelo en esa misma ronda. En el primer ejemplo con k = 1, el precio de la ciudad 2 baja a 100 en la ronda 2, pero no queda ninguna ronda para continuar hasta la ciudad 3 por 150.
Cada ronda lee cada vuelo una vez: tiempo O(k · E) para E vuelos y espacio O(n) para los dos arreglos.
Algoritmo
- Establece
cost[src] = 0y asigna infinito a todos los demás valores decost. - Repite
k+1veces: copiacostennext. - Para cada vuelo
[a, b, price]en el quecost[a]sea finito, sicost[a] + price < next[b], establecenext[b] = cost[a] + price. - Reemplaza
costpornexty detente antes si nada cambió. - Devuelve
cost[dst]o -1 si todavía es infinito.
def findCheapestPrice(n, flights, src, dst, k):
INF = float("inf")
# cost[c]: the cheapest price to reach city c with the flights allowed so far.
cost = [INF] * n
cost[src] = 0
# Each round allows one more flight; k stops means k+1 flights.
for _ in range(k + 1):
# Read last round's prices and write into a copy,
# so one round can never chain two flights.
nxt = cost[:]
changed = False
for a, b, price in flights:
if cost[a] != INF and cost[a] + price < nxt[b]:
nxt[b] = cost[a] + price
changed = True
cost = nxt
if not changed:
break
return -1 if cost[dst] == INF else cost[dst]
Errores comunes y casos límite
- Contar las escalas como vuelos.
kescalas significak+1vuelos yk+1rondas. - Actualizar en el mismo lugar. Con
0 → 1,1 → 2,2 → 3por 1 cada uno, en ese orden, más0 → 3por 500 yk = 0, una ronda encadena tres vuelos y devuelve 3, no 500. - Ejecutar Dijkstra normal en las ciudades. Con
0 → 1y1 → 2por 1 cada uno,0 → 2por 40,2 → 3por 1 yk = 1, fija la ciudad 2 en 2 después de dos vuelos y no encuentra0 → 2 → 3por 41. - Volar desde una ciudad no alcanzada. Si infinito es el int más grande,
cost[a] + pricese desborda y se vuelve negativo en 32 bits. Comprueba primero quecost[a]sea finito.
Preguntas frecuentes3
¿Cuál es la complejidad temporal de «Vuelos más baratos con un máximo de K escalas»?
Bellman-Ford limitado a k+1 rondas tarda O(k · E) para E vuelos y usa O(n) de espacio adicional para dos arreglos de precios. Una ronda que no cambia nada entrega los mismos precios a la siguiente, así que puedes detenerte antes.
¿Por qué no funciona el algoritmo de Dijkstra para encontrar los vuelos más baratos con un máximo de K escalas?
Dijkstra conserva un mejor precio por ciudad y nunca vuelve a visitar una ciudad ya fijada. Aquí, una ruta más cara hasta una ciudad puede ser la útil si necesitó menos vuelos. Dijkstra vuelve a funcionar sobre estados (ciudad, vuelos utilizados), lo que multiplica los estados por k+1.
¿Puedes resolver «Vuelos más baratos con hasta K escalas» con BFS?
Sí. El nivel r contiene las ciudades alcanzadas con exactamente r vuelos, junto con sus precios. Coloca una ciudad en el siguiente nivel solo cuando su nuevo precio sea mejor que el mejor precio registrado para ella, y detente después de k+1 niveles. Da la misma respuesta que Bellman-Ford, pero solo sigue los vuelos que salen de ciudades cuyo precio cambió.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
def findCheapestPrice(n, flights, src, dst, k):
# Escribe el código aquíPrueba #1
Prueba #2
Prueba #3
Argumentos
n = 4 flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]] src = 0 dst = 3 k = 1
Salida Esperada
230