Baltic OI '17 P2 - Toll

View as PDF

Submit solution

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

Problem types
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 a to b if \left\lfloor\frac b K\right\rfloor = 1 + \left\lfloor\frac a K\right\rfloor (for some constant K).

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: K (with the meaning described above), N (the number of places), M (the number of streets), and O (the number of orders).

Each of the next M lines contains three integers a, b, t (0 \le a, b < N). This means that there is a (oneway) street from a to b with toll t. You are guaranteed that \left\lfloor\frac b K\right\rfloor = 1 + \left\lfloor\frac a K\right\rfloor is satisfied, and that no two locations are connected by more than one street.

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

Constraints

We always have 1 \le N \le 50\,000, 1 \le O \le 10\,000 and K \le 5. Moreover, we have 0 \le a < b < N for all orders a, b and 1 \le t \le 10\,000 for all tolls t. For subcases, the inputs have these further restrictions:

  • Group 1: 7 points K = 1
  • Group 2: 10 points All orders have a = 0
  • Group 3: 8 points O \le 100
  • Group 4: 31 points O \le 3\,000
  • Group 5: 44 points No further restrictions

Output Specification

Your output should consist of O lines, each with one integer. The i-th line should contain the toll on a cheapest path between the two places in order i. 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

Comments


  • 3
    TechnobladeNeverDies  commented on July 27, 2021, 9:02 a.m. edit 2

    Using divide and conquer, it's possible to solve this problem in \mathcal{O}(nk^2\log n+q(k+\log n)) as opposed to \mathcal{O}((n+qk)k^2\log n) segment tree, but due to rather low constraints on q this isn't much better :(