Cheapest Flights Within K Stops
Há n cidades, numeradas de 0 a n-1, e uma lista de voos só de ida: flights[i] = [from, to, price] é um voo da cidade from para a cidade to que custa price.
Retorne o menor preço total de uma viagem de src até dst que faça no máximo k paradas no caminho, o que significa no máximo k+1 voos. Se não existir uma viagem assim, retorne -1.
Função
- ninteger
- o número de cidades
- flightsinteger-2d-array
- os voos de ida, cada um como [from, to, price]
- srcinteger
- a cidade onde a viagem começa
- dstinteger
- a cidade onde a viagem termina
- kinteger
- o maior número de paradas permitido entre src e dst
- Retornainteger
- o menor preço de uma viagem com no máximo k paradas, ou -1
Restrições
2 ≤ n ≤ 10001 ≤ flights.length ≤ 4500flights[i] = [from, to, price]com0 ≤ from, to < nefrom ≠ to1 ≤ price ≤ 104- Nenhum par de voos compartilha
frometo. 0 ≤ src, dst < nesrc ≠ dst0 ≤ k < n
Exemplos
- Entrada
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 1
- Saída
- 230
- Explicação
- Uma parada permite dois voos:
0 → 1 → 3custa 50 + 180 = 230, e0 → 2 → 3custa 200 + 50 = 250. A opção mais barata,0 → 1 → 2 → 3, faz duas paradas.
- Entrada
- n = 4flights = [[0, 1, 50], [1, 2, 50], [2, 3, 50], [0, 2, 200], [1, 3, 180]]src = 0dst = 3k = 2
- Saída
- 150
- Explicação
- Duas escalas permitem três voos, então
0 → 1 → 2 → 3agora é permitido, e custa 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
- Saída
- -1
- Explicação
- Sem paradas, a viagem precisa ser um único voo de 0 a 3, e não há nenhum.
Para ir além
Como você retornaria as cidades da viagem mais barata e também o preço dela?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
A viagem mais barata no geral pode ter escalas demais, então o caminho mais curto simples não é suficiente. Um preço só é útil junto com o número de voos necessários.
Seja
cost[c]o menor preço para chegar à cidadeccom no máximorvoos. Uma passagem por todos os voos transforma esse valor no menor preço com no máximor+1voos. Você precisa dek+1passagens desse tipo.Em cada passagem, leia os preços da passagem anterior e grave em uma cópia. Se você atualizar no próprio conjunto, um voo pode se basear em um preço definido na mesma passagem, e uma única passagem acaba incluindo dois voos.
Solução
Este é um problema de caminho mais curto com um limite no número de voos. O algoritmo de Dijkstra considerando apenas as cidades falha, porque o caminho mais barato até uma cidade pode consumir escalas necessárias para o restante da viagem. Bellman-Ford se adapta ao limite: a rodada r encontra o menor preço com no máximo r voos, então você executa k+1 rodadas.
Tente todas as rotas com no máximo k+1 voos
Correta, mas não termina nos maiores testes
Intuição
Percorra todas as rotas a partir de src usando uma pilha de (cidade, preço, voos usados). Uma rota que chega a dst registra seu preço e termina, pois todos os preços são positivos. Uma rota com k+1 voos é descartada; qualquer outra é estendida por todos os voos que partem de sua cidade. Todas as viagens permitidas são construídas, então o melhor preço registrado está correto.
As rotas crescem como d elevado à potência k+1, para d voos partindo de uma cidade. Com 4 voos por cidade e k = 29, isso resulta em 4^30 ≈ 1.2 × 10^18 rotas.
Algoritmo
- Agrupe os voos pela cidade de partida.
- Empilhe
(src, 0, 0): cidade, preço até o momento, voos realizados. - Desempilhe uma rota. Se a cidade dela for
dst, mantenha o preço se for o melhor até o momento. - Caso contrário, se ela tiver realizado menos de
k+1voos, empilhe uma rota mais longa para cada voo que sai da cidade dela. - Quando a pilha estiver vazia, retorne o melhor preço ou -1 se nenhuma rota tiver chegado 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 rodadas
Intuição
Seja cost[c] o menor preço para chegar à cidade c com no máximo r voos. Com r = 0, apenas src é alcançável, a um preço de 0. Uma viagem até a com no máximo r voos, seguida de um voo a → b, é uma viagem até b com no máximo r+1 voos; assim, a cada rodada, cada voo oferece cost[a] + price para b. Após k+1 rodadas, cost[dst] é a resposta.
Cada rodada lê os preços da rodada anterior e grava em uma cópia, então um preço definido durante uma rodada não pode alimentar outro voo na mesma rodada. No primeiro exemplo, com k = 1, o preço da cidade 2 cai para 100 na rodada 2, mas não resta nenhuma rodada para seguir de avião até a cidade 3 por 150.
Cada rodada lê cada voo uma vez: tempo O(k · E) para E voos e espaço O(n) para os dois arrays.
Algoritmo
- Defina
cost[src] = 0e todos os outros valores decostcomo infinito. - Repita
k+1vezes: copiecostparanext. - Para cada voo
[a, b, price]em quecost[a]é finito, secost[a] + price < next[b], definanext[b] = cost[a] + price. - Substitua
costpornexte pare antes se nada tiver mudado. - Retorne
cost[dst]ou -1 se ainda for 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]
Armadilhas e casos extremos
- Contar as escalas como voos.
kescalas significamk+1voos ek+1rodadas. - Atualizar no próprio lugar. Com
0 → 1,1 → 2,2 → 3por 1 cada, nessa ordem, além de0 → 3por 500 ek = 0, uma rodada encadeia três voos e retorna 3, não 500. - Executar o Dijkstra simples nas cidades. Com
0 → 1e1 → 2por 1 cada,0 → 2por 40,2 → 3por 1 ek = 1, ele finaliza a cidade 2 com custo 2 após dois voos e não encontra0 → 2 → 3por 41. - Voar partindo de uma cidade não alcançada. Com infinito como o maior int,
cost[a] + pricesofre overflow e se torna negativo em 32 bits. Verifique primeiro secost[a]é finito.
Perguntas frequentes3
Qual é a complexidade de tempo do problema Cheapest Flights Within K Stops?
Bellman-Ford limitado a k+1 rodadas leva O(k · E) de tempo para E voos e O(n) de espaço extra para dois arrays de preços. Uma rodada que não altera nada passa os mesmos preços para a rodada seguinte, então você pode parar antes.
Por que o algoritmo de Dijkstra não funciona para encontrar os voos mais baratos com até K escalas?
Dijkstra mantém um melhor preço por cidade e nunca revisita uma cidade já finalizada. Aqui, um caminho mais caro para chegar a uma cidade pode ser o mais útil quando exigiu menos voos. Dijkstra funciona novamente usando estados (cidade, voos usados), o que multiplica o número de estados por k+1.
Você consegue resolver o problema Cheapest Flights Within K Stops com BFS?
Sim. O nível r contém as cidades alcançadas com exatamente r voos, com seus preços. Coloque uma cidade no próximo nível somente quando seu novo preço for melhor que o melhor já visto para ela, e pare após k+1 níveis. Isso dá a mesma resposta que o Bellman-Ford, mas segue apenas os voos que partem de cidades cujo preço mudou.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def findCheapestPrice(n, flights, src, dst, k):
# Escreva o código aquiTeste #1
Teste #2
Teste #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
Saída Esperada
230