## Baltic OI '17 P2 - Toll

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### Baltic Olympiad in Informatics: 2017 Day 1, Problem 2

A trucking company wants to optimize its internal processes—which mainly means saving money. The company serves a region where a toll must be paid for every single street. Each street connects two places (cities, villages etc.) directly. The company serves a set of orders; each order tells them to carry goods from one place to another. When serving an order, the company wants to pay the minimum overall toll. As the region's street network can be modeled by a graph where each edge has a specific cost (the toll for the respective street), the company actually wants to know (the cost of) the cheapest path between two nodes in this graph.

However, the region's street network graph has an interesting property: it is directed (i.e. all streets are oneway), and there can only be an edge from to if (for some constant ).

Write a program that for each of a given list of orders outputs the minimum toll the company has to pay to serve the respective order.

#### Input Specification

The first line contains four integers: (with the meaning described above), (the number of places), (the number of streets), and (the number of orders).

Each of the next lines contains three integers , , (). This means that there is a (oneway) street from to with toll . You are guaranteed that is satisfied, and that no two locations are connected by more than one street.

Finally lines follow, each containing two integers , : this means that there is an order to carry goods from place to place .

#### Constraints

We always have , and . Moreover, we have for all orders , and for all tolls . For subcases, the inputs have these further restrictions:

• Group 1: 7 points
• Group 2: 10 points All orders have
• Group 3: 8 points
• Group 4: 31 points
• Group 5: 44 points No further restrictions

#### Output

Your output should consist of lines, each with one integer. The -th line should contain the toll on a cheapest path between the two places in order . If no such path exists, output -1 in this line.

#### Sample Input

5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13

#### Sample Output

15
9
7
8
-1