Problem Statement
There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
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: The graph is shown above. The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700. Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
Example 2:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
Explanation:The graph is shown above. The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.
Example 3:
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500
Explanation: The graph is shown above. The optimal path with no stops from city 0 to 2 is marked in red and has cost 500. .
Constraints
2 <= n <= 1000 <= flights.length <= (n * (n - 1) / 2)flights[i].length == 30 <= fromi, toi < nfromi != toi1 <= pricei <= 104- There will not be any multiple flights between two cities.
0 <= src, dst, k < nsrc != dst
Approach
- Build an
adjacency listfrom the flights array where each city stores its neighbors and travel cost. - Use a BFS-style queue that keeps track of (
current city, total cost, number of stops). - Maintain a
minPricearray to store the cheapest cost found so far to reach each city. - Start from the source city with cost
0and0stops. - While processing the queue:
- Skip paths that exceed
kstops. - For each neighbor, update the cost if a cheaper price is found and push it into the queue with increased stops.
- Skip paths that exceed
- Finally, return the minimum cost to reach dst; if unreachable within k stops,
return -1.
Time & Space Complexity
Time Complexity: O(E x K)
Space Complexity: O(N + E)
Dry Run
Input:
n = 4,
flights = [[0,1,100],[1,2,100],[0,2,500]],
src = 0,
dst = 2,
k = 1
Step 0: Start Function: findCheapestPrice(4, flights, 0, 2, 1) Step 1: Build Graph (Adjacency List) graph = [ [[1, 100], [2, 500]], // 0 [[2, 100]], // 1 [], // 2 [] // 3 ] Step 2: Initialize minPrice array minPrice = [0, Infinity, Infinity, Infinity] Step 3: Initialize Queue q = [[0, 0, 0]] // [city, cost, stops] -------------------------------------------------- Step 4: Start BFS Traversal Dequeue → [0, 0, 0] stops = 0 (≤ k, continue) Explore neighbors of city 0: 1) Neighbor = 1, price = 100 newPrice = 0 + 100 = 100 100 < Infinity → update minPrice = [0, 100, Infinity, Infinity] q = [[1, 100, 1]] 2) Neighbor = 2, price = 500 newPrice = 0 + 500 = 500 500 < Infinity → update minPrice = [0, 100, 500, Infinity] q = [[1, 100, 1], [2, 500, 1]] -------------------------------------------------- Dequeue → [1, 100, 1] stops = 1 (≤ k, continue) Explore neighbors of city 1: 1) Neighbor = 2, price = 100 newPrice = 100 + 100 = 200 200 < 500 → update minPrice = [0, 100, 200, Infinity] q = [[2, 500, 1], [2, 200, 2]] -------------------------------------------------- Dequeue → [2, 500, 1] stops = 1 (≤ k, continue) City 2 has no neighbors → nothing happens -------------------------------------------------- Dequeue → [2, 200, 2] stops = 2 (> k) → skip this path -------------------------------------------------- Step 5: End BFS minPrice = [0, 100, 200, Infinity] Step 6: Return Result minPrice[dst] = minPrice[2] = 200
Output: 200
var findCheapestPrice = function(n, flights, src, dst, k) {
let graph = Array.from({ length: n}, () => []);
for(let [from, to, price] of flights) {
graph[from].push([to, price]);
}
let minPrice = new Array(n).fill(Infinity);
minPrice[src] = 0;
// [city, cost, stops]
let q = [[src, 0, 0]];
while(q.length) {
let [curr, currPrice, stops] = q.shift();
if(stops > k) continue;
for(let [neighbor, neighborPrice] of graph[curr]) {
let newPrice = currPrice + neighborPrice;
if(newPrice < minPrice[neighbor]) {
minPrice[neighbor] = newPrice;
q.push([neighbor, newPrice, stops + 1])
}
}
}
return minPrice[dst] === Infinity ? -1 : minPrice[dst];
};
from collections import deque
from typing import List
def findCheapestPrice(n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
graph = [[] for _ in range(n)]
for u, v, price in flights:
graph[u].append((v, price))
minPrice = [float('inf')] * n
minPrice[src] = 0
q = deque([(src, 0, 0)]) # city, cost, stops
while q:
city, cost, stops = q.popleft()
if stops > k:
continue
for nxt, price in graph[city]:
newPrice = cost + price
if newPrice < minPrice[nxt]:
minPrice[nxt] = newPrice
q.append((nxt, newPrice, stops + 1))
return -1 if minPrice[dst] == float('inf') else minPrice[dst]
import java.util.*;
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
List[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int[] f : flights) {
graph[f[0]].add(new int[]{f[1], f[2]});
}
int[] minPrice = new int[n];
Arrays.fill(minPrice, Integer.MAX_VALUE);
minPrice[src] = 0;
Queue q = new LinkedList<>();
q.offer(new int[]{src, 0, 0}); // city, cost, stops
while (!q.isEmpty()) {
int[] curr = q.poll();
int city = curr[0], cost = curr[1], stops = curr[2];
if (stops > k) continue;
for (int[] nbr : graph[city]) {
int nextCity = nbr[0];
int price = nbr[1];
int newPrice = cost + price;
if (newPrice < minPrice[nextCity]) {
minPrice[nextCity] = newPrice;
q.offer(new int[]{nextCity, newPrice, stops + 1});
}
}
}
return minPrice[dst] == Integer.MAX_VALUE ? -1 : minPrice[dst];
}
}
#include <vector>
#include <queue>
#include <climits>
using namespace std;
int findCheapestPrice(int n, vector>& flights, int src, int dst, int k) {
vector>> graph(n);
for (auto &f : flights) {
graph[f[0]].push_back({f[1], f[2]});
}
vector minPrice(n, INT_MAX);
minPrice[src] = 0;
queue> q;
q.push({src, 0, 0}); // city, cost, stops
while (!q.empty()) {
auto curr = q.front();
q.pop();
int city = curr[0], cost = curr[1], stops = curr[2];
if (stops > k) continue;
for (auto &nbr : graph[city]) {
int nextCity = nbr.first;
int price = nbr.second;
int newPrice = cost + price;
if (newPrice < minPrice[nextCity]) {
minPrice[nextCity] = newPrice;
q.push({nextCity, newPrice, stops + 1});
}
}
}
return minPrice[dst] == INT_MAX ? -1 : minPrice[dst];
}
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct {
int to;
int price;
} Edge;
typedef struct {
Edge edges[1000];
int size;
} GraphNode;
int findCheapestPrice(int n, int flights[][3], int flightsSize, int src, int dst, int k) {
GraphNode graph[100];
for (int i = 0; i < n; i++) graph[i].size = 0;
for (int i = 0; i < flightsSize; i++) {
int from = flights[i][0];
graph[from].edges[graph[from].size++] =
(Edge){flights[i][1], flights[i][2]};
}
int minPrice[100];
for (int i = 0; i < n; i++) minPrice[i] = INT_MAX;
minPrice[src] = 0;
int q[1000][3], front = 0, rear = 0;
q[rear][0] = src;
q[rear][1] = 0;
q[rear][2] = 0;
rear++;
while (front < rear) {
int city = q[front][0];
int cost = q[front][1];
int stops = q[front][2];
front++;
if (stops > k) continue;
for (int i = 0; i < graph[city].size; i++) {
int nextCity = graph[city].edges[i].to;
int price = graph[city].edges[i].price;
int newPrice = cost + price;
if (newPrice < minPrice[nextCity]) {
minPrice[nextCity] = newPrice;
q[rear][0] = nextCity;
q[rear][1] = newPrice;
q[rear][2] = stops + 1;
rear++;
}
}
}
return minPrice[dst] == INT_MAX ? -1 : minPrice[dst];
}
using System;
using System.Collections.Generic;
public class Solution {
public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
var graph = new List<(int, int)>[n];
for (int i = 0; i < n; i++) graph[i] = new List<(int, int)>();
foreach (var f in flights) {
graph[f[0]].Add((f[1], f[2]));
}
int[] minPrice = new int[n];
Array.Fill(minPrice, int.MaxValue);
minPrice[src] = 0;
var q = new Queue<(int city, int cost, int stops)>();
q.Enqueue((src, 0, 0));
while (q.Count > 0) {
var (city, cost, stops) = q.Dequeue();
if (stops > k) continue;
foreach (var (next, price) in graph[city]) {
int newPrice = cost + price;
if (newPrice < minPrice[next]) {
minPrice[next] = newPrice;
q.Enqueue((next, newPrice, stops + 1));
}
}
}
return minPrice[dst] == int.MaxValue ? -1 : minPrice[dst];
}
}
