CCO '14 P2 - King Gruff

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Canadian Computing Competition: 2014 Stage 2, Day 1, Problem 2

King Gruff the Wolf rules over a happy, prosperous land inhabited by adorable Foxen. Unfortunately for them, he is not a nice king at all, and wants to make their lives miserable!

His country has N (1 \le N \le 10^5) cities, with M (0 \le M \le 10^5) roads running amongst them. The i-th road allows one to travel from city X_i to a different city Y_i (1 \le X_i, Y_i \le N), in that direction only, and has a length of L_i (1 \le L_i \le 10^4) and a shutdown cost of C_i (1 \le C_i \le 10^4). There may be multiple roads running between a pair of cities, even in the same direction.

King Gruff particularly dislikes the Foxen living in two different cities A and B (1 \le A, B \le N), and would like to make it more inconvenient (or even impossible) to travel from city A to city B. In particular, he'll select a distance value D (1 \le D \le 10^9), and then simultaneously shut down every single road in his kingdom which is part of at least one path from city A to city B with total length no more than D. For each such road, however, he'll have to dig into his royal treasury and pay its shutdown cost. A path consists of a sequence of roads such that each road (except the first) starts at the city that the previous road ended at, and may visit a city or road multiple times.

Gruff is having trouble making up his mind about what value of D to choose, however - a larger value would make things more inconvenient for his Foxy subjects, but might cost him more money as well! As such, he'll consider Q (1 \le Q \le 10^5) different values, D_1, D_2, \dots, D_Q. For each one, he'd like to know how many tax dollars would need to be spent to shut down all roads which lie on at least one sufficiently short path from city A to city B. Since you don't like Foxen either, you've agreed to help the Wolf write a program to calculate this!

Input Specification

The first line contains 4 integers, each separated by a space:

  • N (1 \le N \le 10^5), the number of cities, followed by
  • M (0 \le M \le 10^5), the number of roads, followed by
  • A (1 \le A \le N), the starting city, followed by
  • B (1 \le B \le N), the ending city.

Each of the next M lines contain four space-separated integers X_i, Y_i, L_i, and C_i describing the road from X_i to Y_i with length L_i and shutdown cost C_i, where 1 \le X_i, Y_i \le N, 1 \le L_i, C_i \le 10^4.

The next line will contain Q (1 \le Q \le 10^5), the number of different distance values to consider.

The next Q lines each contain one integer D_i (1 \le D_i \le 10^9) which is the distance value to consider in shutting down roads.

The following conditions hold for the input data:

  • For test cases worth up to 20% of the points, N \le 500;
  • For test cases worth up to 20% of the points, Q = 1;
  • For test cases worth up to 80% of the points, Q \le 20.

Output Specification

The output consists of Q lines, each with one integer, representing the total cost required to shut down all necessary roads given a distance value of D_i, for i = 1 \dots Q.

Sample Input 1

4 5 1 3
1 2 5 1
1 2 8 50
2 3 2 15
3 1 80 1000
3 4 1 1

Output for Sample Input 1


Explanation of Output for Sample Input 1

The map of the country is illustrated below, with each road labelled with its length only:

If D = 8, the first and the third roads need to be shut down, as they're both part of a path from city 1 to city 3 of length 7. This incurs a total cost of 1 + 15 = 16.

If D = 6, no roads need to be shut down, as no paths from city 1 to city 3 with total length 6 or less exist.

If D = 90, the first three roads all need to be shut down.

If D = 94, the fourth road must additionally be shut down, as it lies on a path from city 1 to city 3 of length exactly 94, consisting of the first, third, fourth, first and then third roads.

Sample Input 2

4 3 1 2
2 1 1 1
3 4 10000 10000
4 3 10000 10000

Sample Output 2


Explanation 2

The map of the country is illustrated below:

As can be seen, the Foxen already have a problem, as no path from city 1 to city 2 exists! As such, for any value of D, King Gruff doesn't need to shut down any roads.


There are no comments at the moment.