787. Cheapest flights

787_solution1_level_bfs.c

#include <limits.h>
#include <stdlib.h>

typedef struct Edge {
  int to, price;
  struct Edge *next;
} Edge;

typedef struct {
  int city, cost;
} State;

int findCheapestPrice(int n, int **flights, int flightsSize,
                      int *flightsColSize, int src, int dst, int k) {
  (void)flightsColSize;
  // adjacency lists as linked lists; one edge node per flight
  Edge **adj = calloc(n, sizeof(Edge *));
  Edge *pool = malloc(flightsSize * sizeof(Edge));
  for (int i = 0; i < flightsSize; i++) {
    pool[i] = (Edge){flights[i][1], flights[i][2], adj[flights[i][0]]};
    adj[flights[i][0]] = &pool[i];
  }

  int *prices = malloc(n * sizeof(int));
  for (int i = 0; i < n; i++)
    prices[i] = INT_MAX;

  // a city can be queued more than once per level, so the buffers grow on demand
  int curCap = flightsSize + 1, nxtCap = flightsSize + 1;
  State *cur = malloc(curCap * sizeof(State));
  State *nxt = malloc(nxtCap * sizeof(State));
  int curSize = 0;
  prices[src] = 0;
  cur[curSize++] = (State){src, 0};

  // BFS by level, one level per flight (at most k + 1 levels)
  for (int flightsUsed = 0; flightsUsed <= k && curSize > 0; flightsUsed++) {
    int nxtSize = 0;
    for (int i = 0; i < curSize; i++) {
      for (Edge *e = adj[cur[i].city]; e; e = e->next) {
        if (cur[i].cost + e->price < prices[e->to]) {
          prices[e->to] = cur[i].cost + e->price;
          if (nxtSize == nxtCap) {
            nxtCap *= 2;
            nxt = realloc(nxt, nxtCap * sizeof(State));
          }
          nxt[nxtSize++] = (State){e->to, prices[e->to]};
        }
      }
    }
    State *t = cur;
    cur = nxt;
    nxt = t;
    int c = curCap;
    curCap = nxtCap;
    nxtCap = c;
    curSize = nxtSize;
  }

  int ans = prices[dst] == INT_MAX ? -1 : prices[dst];
  free(adj);
  free(pool);
  free(prices);
  free(cur);
  free(nxt);
  return ans;
}

787_solution2_bellman_ford.c

#include <limits.h>
#include <stdlib.h>
#include <string.h>

int findCheapestPrice(int n, int **flights, int flightsSize,
                      int *flightsColSize, int src, int dst, int k) {
  (void)flightsColSize; // always 3
  int *prices = malloc(n * sizeof(int));
  int *next = malloc(n * sizeof(int));
  for (int i = 0; i < n; i++)
    prices[i] = INT_MAX;
  prices[src] = 0;

  // Bellman-Ford limited to k + 1 rounds: round i allows i flights
  for (int round = 0; round <= k; round++) {
    memcpy(next, prices, n * sizeof(int)); // reads come from the previous round only
    for (int i = 0; i < flightsSize; i++) {
      int from = flights[i][0], to = flights[i][1], price = flights[i][2];
      if (prices[from] != INT_MAX && prices[from] + price < next[to])
        next[to] = prices[from] + price;
    }
    int *t = prices;
    prices = next;
    next = t;
  }

  int ans = prices[dst] == INT_MAX ? -1 : prices[dst];
  free(prices);
  free(next);
  return ans;
}

787_solution1_level_bfs.cpp

#include <climits>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

class Solution {
public:
  int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst,
                        int k) {
    vector<vector<pair<int, int>>> adj(n); // from -> {to, price}
    for (auto &f : flights)
      adj[f[0]].push_back({f[1], f[2]});

    vector<int> prices(n, INT_MAX);
    queue<pair<int, int>> q; // {city, cost so far}
    prices[src] = 0;
    q.push({src, 0});

    // BFS by level, one level per flight (at most k + 1 levels)
    for (int flightsUsed = 0; flightsUsed <= k && !q.empty(); flightsUsed++) {
      int sz = q.size();
      for (int i = 0; i < sz; i++) {
        auto [c, p] = q.front();
        q.pop();
        for (auto [next, price] : adj[c]) {
          if (p + price < prices[next]) {
            prices[next] = p + price;
            q.push({next, p + price});
          }
        }
      }
    }

    return prices[dst] == INT_MAX ? -1 : prices[dst];
  }
};

787_solution2_bellman_ford.cpp

#include <climits>
#include <vector>

using namespace std;

class Solution {
public:
  int findCheapestPrice(int n, vector<vector<int>> &flights, int src, int dst,
                        int k) {
    vector<int> prices(n, INT_MAX);
    prices[src] = 0;

    // Bellman-Ford limited to k + 1 rounds: round i allows i flights
    for (int round = 0; round <= k; round++) {
      vector<int> next = prices; // reads come from the previous round only
      for (auto &f : flights) {
        int from = f[0], to = f[1], price = f[2];
        if (prices[from] != INT_MAX && prices[from] + price < next[to])
          next[to] = prices[from] + price;
      }
      prices = move(next);
    }

    return prices[dst] == INT_MAX ? -1 : prices[dst];
  }
};

787_solution1_level_bfs.go

package graphs

import "math"

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
    type edge struct{ to, price int }
    type state struct{ city, cost int }

    adj := make([][]edge, n) // from -> {to, price}
    for _, f := range flights {
        adj[f[0]] = append(adj[f[0]], edge{f[1], f[2]})
    }

    prices := make([]int, n)
    for i := range prices {
        prices[i] = math.MaxInt
    }
    q := []state{{src, 0}}
    prices[src] = 0

    // BFS by level, one level per flight (at most k + 1 levels)
    for flightsUsed := 0; flightsUsed <= k && len(q) > 0; flightsUsed++ {
        sz := len(q)
        for i := 0; i < sz; i++ {
            cur := q[0]
            q = q[1:]
            for _, e := range adj[cur.city] {
                if cur.cost+e.price < prices[e.to] {
                    prices[e.to] = cur.cost + e.price
                    q = append(q, state{e.to, cur.cost + e.price})
                }
            }
        }
    }

    if prices[dst] == math.MaxInt {
        return -1
    }
    return prices[dst]
}

787_solution2_bellman_ford.go

package graphs

import "math"

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
    prices := make([]int, n)
    for i := range prices {
        prices[i] = math.MaxInt
    }
    prices[src] = 0

    // Bellman-Ford limited to k + 1 rounds: round i allows i flights
    for round := 0; round <= k; round++ {
        next := append([]int(nil), prices...) // reads come from the previous round only
        for _, f := range flights {
            from, to, price := f[0], f[1], f[2]
            if prices[from] != math.MaxInt && prices[from]+price < next[to] {
                next[to] = prices[from] + price
            }
        }
        prices = next
    }

    if prices[dst] == math.MaxInt {
        return -1
    }
    return prices[dst]
}

787_solution1_level_bfs.java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        List<List<int[]>> adj = new ArrayList<>(); // from -> {to, price}
        for (int i = 0; i < n; i++)
            adj.add(new ArrayList<>());
        for (int[] f : flights)
            adj.get(f[0]).add(new int[] { f[1], f[2] });

        int[] prices = new int[n];
        Arrays.fill(prices, Integer.MAX_VALUE);
        Queue<int[]> q = new ArrayDeque<>(); // {city, cost so far}
        prices[src] = 0;
        q.offer(new int[] { src, 0 });

        // BFS by level, one level per flight (at most k + 1 levels)
        for (int flightsUsed = 0; flightsUsed <= k && !q.isEmpty(); flightsUsed++) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int[] cur = q.poll();
                int c = cur[0], p = cur[1];
                for (int[] e : adj.get(c)) {
                    int next = e[0], price = e[1];
                    if (p + price < prices[next]) {
                        prices[next] = p + price;
                        q.offer(new int[] { next, p + price });
                    }
                }
            }
        }

        return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
    }
}

787_solution2_bellman_ford.java

import java.util.Arrays;

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[] prices = new int[n];
        Arrays.fill(prices, Integer.MAX_VALUE);
        prices[src] = 0;

        // Bellman-Ford limited to k + 1 rounds: round i allows i flights
        for (int round = 0; round <= k; round++) {
            int[] next = prices.clone(); // reads come from the previous round only
            for (int[] f : flights) {
                int from = f[0], to = f[1], price = f[2];
                if (prices[from] != Integer.MAX_VALUE && prices[from] + price < next[to])
                    next[to] = prices[from] + price;
            }
            prices = next;
        }

        return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
    }
}

787_solution1_level_bfs.js

/**
 * @param {number} n
 * @param {number[][]} flights
 * @param {number} src
 * @param {number} dst
 * @param {number} k
 * @return {number}
 */
var findCheapestPrice = function (n, flights, src, dst, k) {
  const adj = Array.from({ length: n }, () => []); // from -> [to, price]
  for (const [f, t, p] of flights) adj[f].push([t, p]);

  const prices = new Array(n).fill(Infinity);
  let q = [[src, 0]]; // [city, cost so far]
  prices[src] = 0;

  // BFS by level, one level per flight (at most k + 1 levels)
  for (let flightsUsed = 0; flightsUsed <= k && q.length > 0; flightsUsed++) {
    // fresh array per level: Array.shift() is O(n)
    const next = [];
    for (const [c, p] of q) {
      for (const [to, price] of adj[c]) {
        if (p + price < prices[to]) {
          prices[to] = p + price;
          next.push([to, p + price]);
        }
      }
    }
    q = next;
  }

  return prices[dst] === Infinity ? -1 : prices[dst];
};

787_solution2_bellman_ford.js

/**
 * @param {number} n
 * @param {number[][]} flights
 * @param {number} src
 * @param {number} dst
 * @param {number} k
 * @return {number}
 */
var findCheapestPrice = function (n, flights, src, dst, k) {
  let prices = new Array(n).fill(Infinity);
  prices[src] = 0;

  // Bellman-Ford limited to k + 1 rounds: round i allows i flights
  for (let round = 0; round <= k; round++) {
    const next = prices.slice(); // reads come from the previous round only
    for (const [from, to, price] of flights)
      if (prices[from] + price < next[to]) next[to] = prices[from] + price;
    prices = next;
  }

  return prices[dst] === Infinity ? -1 : prices[dst];
};

787_solution1_level_bfs.py

from collections import deque
from typing import List


class Solution:
    def findCheapestPrice(
        self, n: int, flights: List[List[int]], src: int, dst: int, k: int
    ) -> int:
        adj = [[] for _ in range(n)]  # from -> (to, price)
        for f, t, p in flights:
            adj[f].append((t, p))

        prices = [float("inf")] * n
        q = deque([(src, 0)])  # (city, cost so far)
        prices[src] = 0

        flights_used = 0
        # BFS by level, one level per flight (at most k + 1 levels)
        while flights_used <= k and q:
            for _ in range(len(q)):
                c, p = q.popleft()
                for nxt, price in adj[c]:
                    if p + price < prices[nxt]:
                        prices[nxt] = p + price
                        q.append((nxt, p + price))
            flights_used += 1

        return -1 if prices[dst] == float("inf") else prices[dst]

787_solution2_bellman_ford.py

from typing import List


class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        prices = [float("inf")] * n
        prices[src] = 0

        # Bellman-Ford limited to k + 1 rounds: round i allows i flights
        for _ in range(k + 1):
            nxt = prices[:]  # reads come from the previous round only
            for frm, to, price in flights:
                if prices[frm] + price < nxt[to]:
                    nxt[to] = prices[frm] + price
            prices = nxt

        return -1 if prices[dst] == float("inf") else prices[dst]

787_solution1_level_bfs.rs

use std::collections::VecDeque;

impl Solution {
    pub fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 {
        let n = n as usize;
        let mut adj = vec![vec![]; n]; // from -> (to, price)
        for f in &flights {
            adj[f[0] as usize].push((f[1] as usize, f[2]));
        }

        let mut prices = vec![i32::MAX; n];
        let mut q = VecDeque::from([(src as usize, 0)]); // (city, cost so far)
        prices[src as usize] = 0;

        let mut flights_used = 0;
        // BFS by level, one level per flight (at most k + 1 levels)
        while flights_used <= k && !q.is_empty() {
            for _ in 0..q.len() {
                let (c, p) = q.pop_front().unwrap();
                for &(next, price) in &adj[c] {
                    if p + price < prices[next] {
                        prices[next] = p + price;
                        q.push_back((next, p + price));
                    }
                }
            }
            flights_used += 1;
        }

        if prices[dst as usize] == i32::MAX { -1 } else { prices[dst as usize] }
    }
}

787_solution2_bellman_ford.rs

impl Solution {
    pub fn find_cheapest_price(n: i32, flights: Vec<Vec<i32>>, src: i32, dst: i32, k: i32) -> i32 {
        let mut prices = vec![i32::MAX; n as usize];
        prices[src as usize] = 0;

        // Bellman-Ford limited to k + 1 rounds: round i allows i flights
        for _ in 0..=k {
            let mut next = prices.clone(); // reads come from the previous round only
            for f in &flights {
                let (from, to, price) = (f[0] as usize, f[1] as usize, f[2]);
                if prices[from] != i32::MAX && prices[from] + price < next[to] {
                    next[to] = prices[from] + price;
                }
            }
            prices = next;
        }

        if prices[dst as usize] == i32::MAX { -1 } else { prices[dst as usize] }
    }
}