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 will contain 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
4
8
6
90
94

Sample Output 1

16
0
66
1066

Explanation of Sample Output 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
1
1000000000

Sample Output 2

0

Explanation of Sample Output 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.