P6190 [NOI Online #1 Junior] Magic

Country C consists of $n$ cities and $m$ directed roads. Both cities and roads are numbered starting from $1$. Traversing road $i$ costs $t_i$. Now you want to travel from city $1$ to city $n$. You may cast magic at most $k$ times, so that when you traverse the next road, the cost becomes the opposite of the original, i.e. the cost changes from $t_i$ to $-t_i$. Please compute the minimum total cost needed to finish this trip. Note: Casting magic only changes the cost for one traversal, and does not change the road’s own $t_i$. The final total cost may be negative, and a city may be visited multiple times (including city $n$).

The first line contains three integers, representing the number of cities $n$, the number of roads $m$, and the limit on the number of times you can cast magic $k$. Lines $2$ to $(m + 1)$ each contain three integers. On line $(i + 1)$, the integers $u_i, v_i, t_i$ indicate that there is a one-way road from $u_i$ to $v_i$, and traversing it costs $t_i$.

Output one integer in one line, representing the minimum total cost.

#### Explanation for Sample Input/Output 1 Traverse road $1$, road $2$, and road $3$ in order, and cast magic before traversing roads $1$ and $2$. #### Explanation for Sample Input/Output 2 Traverse road $1$, road $2$, and road $1$ in order, and cast magic before both times you traverse road $1$. #### Constraints This problem has $20$ test points. The information for each test point is shown in the table below. | Test Point ID | $n \leq$ | $m \leq$ | $k \leq$ | Acyclic | | :----------: | :--------: | :---------: | :--------: | :----: | | $1 \sim 2$ | $5$ | $20$ | $0$ | Not guaranteed | | $3 \sim 4$ | $10$ | $20$ | $50$ | Not guaranteed | | $5 \sim 6$ | $10$ | $20$ | $0$ | Not guaranteed | | $7 \sim 8$ | $20$ | $200$ | $50$ | Yes | | $9 \sim 10$ | $20$ | $200$ | $0$ | Not guaranteed | | $11 \sim 12$ | $100$ | $200$ | $50$ | Yes | | $13 \sim 14$ | $100$ | $200$ | $50$ | Not guaranteed | | $15 \sim 18$ | $100$ | $2500$ | $1000$ | Not guaranteed | | $19 \sim 20$ | $100$ | $2500$ | $10^6$ | Not guaranteed | For test points where the “Acyclic” column is “Yes”, it is guaranteed that the given graph is a directed acyclic graph; otherwise, there is no guarantee about the graph structure. For all test points, it is guaranteed that: - $1 \leq n \leq 100$, $1 \leq m \leq 2500$, $0 \leq k \leq 10^6$. - $1 \leq u_i, v_i \leq n$, $1 \leq t_i \leq 10^9$. - The given graph has no multiple edges or self-loops, and there exists at least one path from $1$ to $n$. **Unofficial testdata is generated within 5 minutes using [CYaRon](https://github.com/luogu-dev/cyaron). If you find any issues with the testdata, please post in the discussion board or send a private message to @[StudyingFather](/user/22030).** Translated by ChatGPT 5