2014 Canadian Computing Competition, Stage 2

Day 1, Problem 2: King Gruff

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 ≤ N ≤ 105) cities, with M (0 ≤ M ≤ 105) roads running amongst them. The i-th road allows one to travel from city Xi to a different city Yi (1 ≤ Xi, Yi ≤ N), in that direction only, and has a length of Li (1 ≤ Li ≤ 104) and a shutdown cost of Ci (1 ≤ Ci ≤ 104). 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 ≤ A, B ≤ 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 ≤ D ≤ 109), 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 ≤ Q ≤ 105) different values, D1, D2, …, DQ. 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're agreed to help the Wolf write a program to calculate this!

Input

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

  • N (1 ≤ N ≤ 105), the number of cities, followed by
  • M (1 ≤ M ≤ 105), the number of roads, followed by
  • A (1 ≤ A ≤ N), the starting city, followed by
  • B (1 ≤ B ≤ N), the ending city

Each of the next M lines contain four space-separated integers Xi, Yi, Li, and Ci, describing the road from Xi to Yi with length Li, and shutdown cost Ci (where 1 ≤ Xi, Yi ≤ N, 1 ≤ Li, Ci ≤ 104).

The next line contains Q (1 ≤ Q ≤ 105), the number of different distance values to consider.

The next Q lines each contain one integer Di (1 ≤ Di ≤ 109), 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 ≤ 500;
  • For test cases worth up to 20% of the points, Q = 1;
  • For test cases worth up to 80% of the points, Q ≤ 20.

Output

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 Di, for i = 1..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
4
8
6
90
94

Sample Output 1

16
0
66
1066

Explanation of Sample 1

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

If D = 8, the first and 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
1
1000000000

Sample Output 2

0

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.

All Submissions
Best Solutions


Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: May 17, 2014
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...