COCI '21 Contest 4 #2 Autobus

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

In a country there are n cities. The cities are connected by m bus routes, where the i^\text{th} route starts in city a_i, ends in city b_i and takes t_i minutes.

Ema loves to travel, but doesn't like transferring between buses. On her trip she wants to use at most k different bus routes.

Help her answer q questions of the form "What is the shortest travel time to get from city c_j to city d_j (using at most k different bus routes)?".

Input Specification

The first line contains two positive integers n and m (2 \le n \le 70, 1 \le m \le 10^6), the number of cities and the number of bus routes.

The i^\text{th} of the next m lines contains positive integers a_i, b_i, and t_i (1 \le a_i, b_i \le n, 1 \le t_i \le 10^6), the terminal cities and the travel time of the i^\text{th} bus route.

The next line contains two positive integers k and q (1 \le k \le 10^9, 1 \le q \le n^2), the maximum number of used routes and the number of queries.

The j^\text{th} of the next q lines contains positive integers c_j and d_j (1 \le c_j, d_j \le n), the cities from the j^\text{th} query.

Output Specification

Print q lines. In the j^\text{th} line, print the shortest travel time from the j^\text{th} query, or -1 if there is no trip that satisfies the requirements.

Constraints

SubtaskPointsConstraints
115k \le n \le 7
215k \le 3
325k \le n
415No additional constraints.

Sample Input 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

Sample Output 1

10
-1
0

Explanation for Sample Output 1

The answer to the first query from each example is marked on the graph.

Sample Input 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

Sample Output 2

6
4
0

Sample Input 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

Sample Output 3

3
4
0

Comments

There are no comments at the moment.