COCI '21 Contest 4 #2 Autobus

View as PDF

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

Problem type

In a country there are cities. The cities are connected by bus routes, where the route starts in city , ends in city and takes minutes.

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

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

Input Specification

The first line contains two positive integers and , the number of cities and the number of bus routes.

The of the next lines contains positive integers , , and , the terminal cities and the travel time of the bus route.

The next line contains two positive integers and , the maximum number of used routes and the number of queries.

The of the next lines contains positive integers and , the cities from the query.

Output Specification

Print lines. In the line, print the shortest travel time from the query, or -1 if there is no trip that satisfies the requirements.

115
215
325

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