P4467 [SCOI2007] k-th Shortest Path

There are $n$ cities and $m$ directed roads, with cities numbered from $1$ to $n$. Each road connects two different cities, and for any two roads, either their starting cities differ or their ending cities differ. Therefore, $n$ and $m$ satisfy $m \le n(n-1)$. Given two cities $a$ and $b$, you can sort all simple paths (each city appears at most once, including the start and end) from $a$ to $b$: first by total length in ascending order, and if lengths are equal, by lexicographical order in ascending order. Your task is to find the $k$-th shortest path from $a$ to $b$.

The first line contains five positive integers $n, m, k, a, b$. Each of the following $m$ lines contains three integers $u, v, l$, indicating there is a directed road from city $u$ to city $v$ with length $l$.

If there are fewer than $k$ simple paths from $a$ to $b$, output `No`. Otherwise, output the $k$-th shortest path: starting from city $a$, output each visited city in order until city $b$, separated by hyphens `-`.

In the first example, there are $5$ cities and all possible roads exist. There are $5$ simple paths from city $1$ to city $5$, sorted as follows:  - 20% of the testdata: $n \le 5$. - 40% of the testdata: $n \le 30$. - 100% of the testdata: $2 \le n \le 50$, $1 \le k \le 200$, $1 \le l \le 10^4$. Translated by ChatGPT 5