K-th shortest walk

Write codeHard35 min

Your task

You are given a directed graph on n nodes as edges [u, v, w] with positive integer weights, a source s, a target t, and an integer k. Return the length of the k-th shortest WALK from s to t, where walks may repeat nodes and edges and the same length may be achieved by different walks (each counted separately). Order walks by total length ascending; return the k-th value. Return -1 if fewer than k such walks exist. Constraints: up to 50 nodes; weights are positive (so no zero-cost cycles); k up to a few hundred.

Examples

kth_shortest(n: int, edges: list[list[int]], s: int, t: int, k: int) -> int
Example 1
Inputkth_shortest(3, [[0, 1, 1], [1, 2, 1], [1, 1, 2]], 0, 2, 2)
Output4