P4568 [JLOI2011] Flight Routes

Alice and Bob are going to travel by plane, and they chose a relatively cheap airline. This airline operates in $n$ cities, labeled $0$ to $n-1$, and there are $m$ routes. Each route connects two cities and has a certain price. Alice and Bob need to travel from one city to another along these routes, and they may transfer. The airline offers a discount for this trip: they can take flights on at most $k$ routes for free. What is the minimum total cost for their trip?

The first line contains three integers $n, m, k$, representing the number of cities, the number of routes, and the maximum number of free rides, respectively. The next line contains two integers $s, t$, representing the starting city and the destination city. The next $m$ lines each contain three integers $a, b, c$, indicating that there is a bidirectional route between cities $a$ and $b$ with price $c$.

Output a single integer on one line, which is the minimum total cost.

#### Constraints For $30\%$ of the testdata, $2 \le n \le 50$, $1 \le m \le 300$, $k=0$. For $50\%$ of the testdata, $2 \le n \le 600$, $1 \le m \le 6\times10^3$, $0 \le k \le 1$. For $100\%$ of the testdata, $2 \le n \le 10^4$, $1 \le m \le 5\times 10^4$, $0 \le k \le 10$, $0 \le s,t,a,b < n$, $a \ne b$, $0 \le c \le 10^3$. There is also a set of hack testdata. Translated by ChatGPT 5