Shortest Paths

import heapq
import math


def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
    """Time for a signal sent from node `k` to reach all `n` nodes (labeled 1..n),
    where each [u, v, w] in `times` is a directed edge that takes w to cross.
    -1 if some node never hears it."""
    graph: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]  # Index 0 unused.
    for u, v, w in times:
        graph[u].append((v, w))
    dist = [math.inf] * (n + 1)
    dist[k] = 0
    pq = [(0, k)]  # (time, node), earliest first.
    while pq:
        d, node = heapq.heappop(pq)
        if d > dist[node]:
            continue  # Stale entry: node was already settled sooner.
        for neighbor, w in graph[node]:
            if d + w < dist[neighbor]:
                dist[neighbor] = d + w
                heapq.heappush(pq, (dist[neighbor], neighbor))
    # Everyone has the signal once the last node to hear it does.
    slowest = 0
    for node in range(1, n + 1):
        slowest = max(slowest, dist[node])
    return -1 if slowest == math.inf else int(slowest)


if __name__ == "__main__":
    print(network_delay_time([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2))  # 2
    print(network_delay_time([[1, 2, 1]], 2, 1))  # 1
    print(network_delay_time([[1, 2, 1]], 2, 2))  # -1
    print(network_delay_time([[1, 2, 4], [1, 3, 1], [3, 2, 2]], 3, 1))  # 3

// Time for a signal sent from node k to reach all n nodes (labeled 1..n),
// where each [u, v, w] in times is a directed edge that takes w to cross.
// -1 if some node never hears it.
export function networkDelayTime(times: number[][], n: number, k: number): number {
  const graph: [number, number][][] = Array.from({ length: n + 1 }, () => []); // Index 0 unused.
  for (const [u, v, w] of times) graph[u].push([v, w]);
  const dist = new Array<number>(n + 1).fill(Infinity);
  dist[k] = 0;
  const pq: [number, number][] = [[0, k]]; // [time, node], earliest first.
  while (pq.length > 0) {
    const [d, node] = heapPop(pq);
    if (d > dist[node]) continue; // Stale entry: node was already settled sooner.
    for (const [neighbor, w] of graph[node]) {
      if (d + w < dist[neighbor]) {
        dist[neighbor] = d + w;
        heapPush(pq, [dist[neighbor], neighbor]);
      }
    }
  }
  // Everyone has the signal once the last node to hear it does.
  let slowest = 0;
  for (let node = 1; node <= n; node++) slowest = Math.max(slowest, dist[node]);
  return slowest === Infinity ? -1 : slowest;
}

// TypeScript has no built-in priority queue, so here's a small binary
// min-heap of [time, node] pairs, ordered by time.
function heapPush(heap: [number, number][], item: [number, number]): void {
  heap.push(item);
  let i = heap.length - 1;
  while (i > 0) {
    const parent = (i - 1) >> 1;
    if (heap[parent][0] <= heap[i][0]) break;
    [heap[parent], heap[i]] = [heap[i], heap[parent]];
    i = parent;
  }
}

function heapPop(heap: [number, number][]): [number, number] {
  const top = heap[0];
  const last = heap.pop()!;
  if (heap.length > 0) {
    heap[0] = last; // Move the last leaf to the root, then sift it down.
    let i = 0;
    while (2 * i + 1 < heap.length) {
      let child = 2 * i + 1;
      if (child + 1 < heap.length && heap[child + 1][0] < heap[child][0]) child++;
      if (heap[i][0] <= heap[child][0]) break;
      [heap[i], heap[child]] = [heap[child], heap[i]];
      i = child;
    }
  }
  return top;
}

console.log(networkDelayTime([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2)); // 2
console.log(networkDelayTime([[1, 2, 1]], 2, 1)); // 1
console.log(networkDelayTime([[1, 2, 1]], 2, 2)); // -1
console.log(networkDelayTime([[1, 2, 4], [1, 3, 1], [3, 2, 2]], 3, 1)); // 3

package main

import (
	"container/heap"
	"fmt"
	"math"
)

// networkDelayTime returns the time for a signal sent from node k to reach all
// n nodes (labeled 1..n), where each [u, v, w] in times is a directed edge
// that takes w to cross. It returns -1 if some node never hears it.
func networkDelayTime(times [][]int, n int, k int) int {
	graph := make([][][2]int, n+1) // Index 0 unused.
	for _, t := range times {
		u, v, w := t[0], t[1], t[2]
		graph[u] = append(graph[u], [2]int{v, w})
	}
	dist := make([]int, n+1)
	for i := range dist {
		dist[i] = math.MaxInt
	}
	dist[k] = 0
	pq := &minHeap{{0, k}} // [time, node], earliest first.
	for pq.Len() > 0 {
		top := heap.Pop(pq).([2]int)
		d, node := top[0], top[1]
		if d > dist[node] {
			continue // Stale entry: node was already settled sooner.
		}
		for _, e := range graph[node] {
			neighbor, w := e[0], e[1]
			if d+w < dist[neighbor] {
				dist[neighbor] = d + w
				heap.Push(pq, [2]int{dist[neighbor], neighbor})
			}
		}
	}
	// Everyone has the signal once the last node to hear it does.
	slowest := 0
	for node := 1; node <= n; node++ {
		slowest = max(slowest, dist[node])
	}
	if slowest == math.MaxInt {
		return -1
	}
	return slowest
}

// minHeap holds [time, node] pairs for container/heap, earliest first.
type minHeap [][2]int

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)        { *h = append(*h, x.([2]int)) }
func (h *minHeap) Pop() any {
	old := *h
	top := old[len(old)-1]
	*h = old[:len(old)-1]
	return top
}

func main() {
	fmt.Println(networkDelayTime([][]int{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2)) // 2
	fmt.Println(networkDelayTime([][]int{{1, 2, 1}}, 2, 1))                       // 1
	fmt.Println(networkDelayTime([][]int{{1, 2, 1}}, 2, 2))                       // -1
	fmt.Println(networkDelayTime([][]int{{1, 2, 4}, {1, 3, 1}, {3, 2, 2}}, 3, 1)) // 3
}

using System;
using System.Collections.Generic;

public class Solution
{
    // Time for a signal sent from node k to reach all n nodes (labeled 1..n),
    // where each [u, v, w] in times is a directed edge that takes w to cross.
    // -1 if some node never hears it.
    public static int NetworkDelayTime(int[][] times, int n, int k)
    {
        var graph = new List<List<(int, int)>>(); // Index 0 unused.
        for (int i = 0; i <= n; i++) graph.Add(new List<(int, int)>());
        foreach (var t in times)
        {
            int u = t[0], v = t[1], w = t[2];
            graph[u].Add((v, w));
        }
        var dist = new int[n + 1];
        Array.Fill(dist, int.MaxValue);
        dist[k] = 0;
        var pq = new PriorityQueue<int, int>(); // Nodes, earliest time first.
        pq.Enqueue(k, 0);
        while (pq.TryDequeue(out int node, out int d))
        {
            if (d > dist[node]) continue; // Stale entry: node was already settled sooner.
            foreach (var (neighbor, w) in graph[node])
            {
                if (d + w < dist[neighbor])
                {
                    dist[neighbor] = d + w;
                    pq.Enqueue(neighbor, dist[neighbor]);
                }
            }
        }
        // Everyone has the signal once the last node to hear it does.
        int slowest = 0;
        for (int node = 1; node <= n; node++) slowest = Math.Max(slowest, dist[node]);
        return slowest == int.MaxValue ? -1 : slowest;
    }

    public static void Main()
    {
        Console.WriteLine(NetworkDelayTime([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2)); // 2
        Console.WriteLine(NetworkDelayTime([[1, 2, 1]], 2, 1)); // 1
        Console.WriteLine(NetworkDelayTime([[1, 2, 1]], 2, 2)); // -1
        Console.WriteLine(NetworkDelayTime([[1, 2, 4], [1, 3, 1], [3, 2, 2]], 3, 1)); // 3
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Solution {
    // Time for a signal sent from node k to reach all n nodes (labeled 1..n),
    // where each [u, v, w] in times is a directed edge that takes w to cross.
    // -1 if some node never hears it.
    static int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> graph = new ArrayList<>(); // Index 0 unused.
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        for (int[] t : times) {
            int u = t[0], v = t[1], w = t[2];
            graph.get(u).add(new int[] {v, w});
        }
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        // [time, node], earliest first.
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        pq.add(new int[] {0, k});
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int d = top[0], node = top[1];
            if (d > dist[node]) continue; // Stale entry: node was already settled sooner.
            for (int[] e : graph.get(node)) {
                int neighbor = e[0], w = e[1];
                if (d + w < dist[neighbor]) {
                    dist[neighbor] = d + w;
                    pq.add(new int[] {dist[neighbor], neighbor});
                }
            }
        }
        // Everyone has the signal once the last node to hear it does.
        int slowest = 0;
        for (int node = 1; node <= n; node++) slowest = Math.max(slowest, dist[node]);
        return slowest == Integer.MAX_VALUE ? -1 : slowest;
    }

    public static void main(String[] args) {
        System.out.println(networkDelayTime(new int[][] {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2)); // 2
        System.out.println(networkDelayTime(new int[][] {{1, 2, 1}}, 2, 1)); // 1
        System.out.println(networkDelayTime(new int[][] {{1, 2, 1}}, 2, 2)); // -1
        System.out.println(networkDelayTime(new int[][] {{1, 2, 4}, {1, 3, 1}, {3, 2, 2}}, 3, 1)); // 3
    }
}

import math


def find_cheapest_price(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    """Cheapest price from `src` to `dst` using at most `k` stops (so at most k + 1
    flights), where each flight is [u, v, price]. -1 if no such route exists."""
    prices = [math.inf] * n
    prices[src] = 0
    # After round i, prices[v] is the cheapest way to reach v in at most i flights.
    for _ in range(k + 1):
        # Read last round's prices and write into a copy. Updating in place would let
        # one round chain several flights and slip past the stop limit.
        next_prices = prices.copy()
        for u, v, price in flights:
            # Only fly out of cities an earlier round already reached.
            if prices[u] != math.inf and prices[u] + price < next_prices[v]:
                next_prices[v] = prices[u] + price
        prices = next_prices
    return -1 if prices[dst] == math.inf else int(prices[dst])


if __name__ == "__main__":
    print(find_cheapest_price(4, [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], 0, 3, 1))  # 700
    print(find_cheapest_price(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 1))  # 200
    print(find_cheapest_price(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 0))  # 500
    print(find_cheapest_price(3, [[0, 1, 100], [1, 2, 100]], 0, 2, 0))  # -1

// Cheapest price from src to dst using at most k stops (so at most k + 1
// flights), where each flight is [u, v, price]. -1 if no such route exists.
export function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
  let prices = new Array<number>(n).fill(Infinity);
  prices[src] = 0;
  // After round i, prices[v] is the cheapest way to reach v in at most i flights.
  for (let round = 1; round <= k + 1; round++) {
    // Read last round's prices and write into a copy. Updating in place would let
    // one round chain several flights and slip past the stop limit.
    const nextPrices = [...prices];
    for (const [u, v, price] of flights) {
      // Only fly out of cities an earlier round already reached.
      if (prices[u] !== Infinity && prices[u] + price < nextPrices[v]) {
        nextPrices[v] = prices[u] + price;
      }
    }
    prices = nextPrices;
  }
  return prices[dst] === Infinity ? -1 : prices[dst];
}

console.log(findCheapestPrice(4, [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], 0, 3, 1)); // 700
console.log(findCheapestPrice(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 1)); // 200
console.log(findCheapestPrice(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 0)); // 500
console.log(findCheapestPrice(3, [[0, 1, 100], [1, 2, 100]], 0, 2, 0)); // -1

package main

import (
	"fmt"
	"math"
	"slices"
)

// findCheapestPrice returns the cheapest price from src to dst using at most
// k stops (so at most k + 1 flights), where each flight is [u, v, price]. It
// returns -1 if no such route exists.
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
	// After round i, prices[v] is the cheapest way to reach v in at most i flights.
	for round := 1; round <= k+1; round++ {
		// Read last round's prices and write into a copy. Updating in place would let
		// one round chain several flights and slip past the stop limit.
		nextPrices := slices.Clone(prices)
		for _, f := range flights {
			u, v, price := f[0], f[1], f[2]
			// Only fly out of cities an earlier round already reached.
			if prices[u] != math.MaxInt && prices[u]+price < nextPrices[v] {
				nextPrices[v] = prices[u] + price
			}
		}
		prices = nextPrices
	}
	if prices[dst] == math.MaxInt {
		return -1
	}
	return prices[dst]
}

func main() {
	fmt.Println(findCheapestPrice(4, [][]int{{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}}, 0, 3, 1)) // 700
	fmt.Println(findCheapestPrice(3, [][]int{{0, 1, 100}, {1, 2, 100}, {0, 2, 500}}, 0, 2, 1))                           // 200
	fmt.Println(findCheapestPrice(3, [][]int{{0, 1, 100}, {1, 2, 100}, {0, 2, 500}}, 0, 2, 0))                           // 500
	fmt.Println(findCheapestPrice(3, [][]int{{0, 1, 100}, {1, 2, 100}}, 0, 2, 0))                                        // -1
}

using System;

public class Solution
{
    // Cheapest price from src to dst using at most k stops (so at most k + 1
    // flights), where each flight is [u, v, price]. -1 if no such route exists.
    public static int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k)
    {
        var prices = new int[n];
        Array.Fill(prices, int.MaxValue);
        prices[src] = 0;
        // After round i, prices[v] is the cheapest way to reach v in at most i flights.
        for (int round = 1; round <= k + 1; round++)
        {
            // Read last round's prices and write into a copy. Updating in place would let
            // one round chain several flights and slip past the stop limit.
            var nextPrices = (int[])prices.Clone();
            foreach (var flight in flights)
            {
                int u = flight[0], v = flight[1], price = flight[2];
                // Only fly out of cities an earlier round already reached.
                if (prices[u] != int.MaxValue && prices[u] + price < nextPrices[v])
                {
                    nextPrices[v] = prices[u] + price;
                }
            }
            prices = nextPrices;
        }
        return prices[dst] == int.MaxValue ? -1 : prices[dst];
    }

    public static void Main()
    {
        Console.WriteLine(FindCheapestPrice(4, [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]], 0, 3, 1)); // 700
        Console.WriteLine(FindCheapestPrice(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 1)); // 200
        Console.WriteLine(FindCheapestPrice(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 0)); // 500
        Console.WriteLine(FindCheapestPrice(3, [[0, 1, 100], [1, 2, 100]], 0, 2, 0)); // -1
    }
}

import java.util.Arrays;

public class Solution {
    // Cheapest price from src to dst using at most k stops (so at most k + 1
    // flights), where each flight is [u, v, price]. -1 if no such route exists.
    static 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;
        // After round i, prices[v] is the cheapest way to reach v in at most i flights.
        for (int round = 1; round <= k + 1; round++) {
            // Read last round's prices and write into a copy. Updating in place would let
            // one round chain several flights and slip past the stop limit.
            int[] nextPrices = prices.clone();
            for (int[] flight : flights) {
                int u = flight[0], v = flight[1], price = flight[2];
                // Only fly out of cities an earlier round already reached.
                if (prices[u] != Integer.MAX_VALUE && prices[u] + price < nextPrices[v]) {
                    nextPrices[v] = prices[u] + price;
                }
            }
            prices = nextPrices;
        }
        return prices[dst] == Integer.MAX_VALUE ? -1 : prices[dst];
    }

    public static void main(String[] args) {
        System.out.println(findCheapestPrice(4, new int[][] {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}}, 0, 3, 1)); // 700
        System.out.println(findCheapestPrice(3, new int[][] {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}}, 0, 2, 1)); // 200
        System.out.println(findCheapestPrice(3, new int[][] {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}}, 0, 2, 0)); // 500
        System.out.println(findCheapestPrice(3, new int[][] {{0, 1, 100}, {1, 2, 100}}, 0, 2, 0)); // -1
    }
}