P8312 [COCI 2021/2022 #4] Autobus

In a country, there are $n$ cities. These cities are connected by $m$ bus routes. The $i$-th route starts from city $a_i$ and stops at city $b_i$, and it takes $t_i$ minutes along the way. Ema likes traveling, but she does not like transferring between bus routes. During a trip, she wants to take **at most** $k$ different bus routes. Ema wants to know the shortest travel time from city $c_i$ to city $d_i$ (using at most $k$ different bus routes).

The first line contains two integers $n, m$, representing the number of cities and the number of bus routes. The next $m$ lines describe the routes. The $(i+1)$-th line contains three integers $a_i, b_i, t_i$, representing the start city, the end city, and the time needed from the start to the end for the $i$-th bus route. The next line contains two integers $k, q$, representing the maximum number of different bus routes that can be taken, and the number of queries. The next $q$ lines describe the queries. The $(m+j+3)$-th line contains two integers $c_j, d_j$, asking for the shortest travel time from city $c_j$ to city $d_j$.

Output $q$ lines. The $i$-th line contains one integer, the shortest travel time from city $c_i$ to city $d_i$.

**Sample Explanation.**  In each sample, the answers have been marked in the figure. **Constraints.** **This problem uses bundled subtasks.** - Subtask 1 (15 pts): $k \le n \le 7$. - Subtask 2 (15 pts): $k \le 3$. - Subtask 3 (25 pts): $k \le n$. - Subtask 4 (15 pts): No additional constraints. For $100\%$ of the testdata, $2 \le n \le 70$, $1 \le m, t_i \le 10^6$, $1 \le a_i, b_i, c_j, d_j \le n$, $1 \le k \le 10^9$, and $1 \le q \le n^2$. **Hints and Notes.** **The score setting follows the original COCI problem, with a full score of $70$.** **Translated from [COCI2021-2022](https://hsin.hr/coci/) [CONTEST #4](https://hsin.hr/coci/contest4_tasks.pdf) T2 Autobus.** Translated by ChatGPT 5