Shortest path with edge limit
Your task
Given a directed weighted graph with n nodes (0..n-1), edges [u, v, w] (non-negative weights), a source src, a destination dst, and an integer K, return the minimum total weight of a path from src to dst that uses AT MOST K edges, or -1 if no such path exists. K may be 0 (then only src reaches itself). Assume 1 <= n <= 500 and K <= n; a layered Bellman-Ford-style relaxation (not plain Dijkstra) is the intended approach.
Examples
shortest_path_max_edges(n: int, edges: list[list[int]], src: int, dst: int, K: int) -> intExample 1
Input
shortest_path_max_edges(4, [[0, 1, 100], [1, 2, 100], [0, 2, 500], [2, 3, 100]], 0, 3, 2)Output
600