题目描述
Problem Description
In a country, there are $n$ cities connected by $m$ bus routes. The $i$-th route starts from city $a_i$ and ends at city $b_i$, taking $t_i$ minutes to travel.
Ema loves traveling but dislikes transferring between bus routes. During her journey, she wishes to use 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).
Input Format
The first line contains two integers $n$ and $m$, representing the number of cities and the number of bus routes, respectively.
The next $m$ lines, the $(i+1)$-th line contains three integers $a_i$, $b_i$, and $t_i$, representing the start city, end city, and travel time of the $i$-th bus route.
The next line contains two integers $k$ and $q$, the maximum number of different bus routes Ema is willing to use and the number of queries.
The next $q$ lines, the $(m+j+3)$-th line contains two integers $c_j$ and $d_j$, representing the query for the shortest travel time from city $c_j$ to city $d_j$.
Output Format
The output contains $q$ lines. The $i$-th line contains an integer representing the shortest travel time from city $c_i$ to city $d_i$.
Sample Input and Output
Input Sample #1
4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
1 3
1 4
4 2
3 3
Output Sample #1
10
-1
0
Input Sample #2
4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
2 3
1 4
4 2
3 3
Output Sample #2
6
4
0
Input Sample #3
4 7
1 2 1
1 4 10
2 3 1
2 4 5
3 2 2
3 4 1
4 3 2
3 3
1 4
4 2
3 3
Output Sample #3
3
4
0
Notes
[Sample Explanation]
The answers for each sample are marked in the diagram.
[Data Range and Constraints]
This problem uses subtask-based scoring.
- Subtask 1 (15 pts): $k ≤ n ≤ 7$.
- Subtask 2 (15 pts): $k ≤ 3$.
- Subtask 3 (25 pts): $k ≤ n$.
- Subtask 4 (15 pts): No additional constraints.
For $100\%$ of the data, $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, 1\le q \le n^2$.
[Hints and Clarifications]
This problem is scored according to the original COCI settings, with a full score of $70$.
The problem is translated from COCI2021-2022 CONTEST #4 T2 Autobus.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分