TLE '16 Contest 6 (Mock CCC) S5 - Toll Routes


Submit solution


Points:20 (partial)
Time limit:4.0s
Java10.0s
Python15.0s
Memory limit:512M
Java512M
Python512M

Problem type

Fax McClad flying over a toll route while towing a microwave to be delivered.

Fax McClad, Croneria's most profitable bounty hunter, has a part-time job delivering microwaves.

Croneria has N cities - numbered from 1 to N. M toll routes connect the cities. The i^{th} toll route costs t_i Cronerian Moneys to travel on and allows a one-way connection from city u_i to city v_i. An interesting thing to note about the Cronerian Toll Route system is that it is impossible to visit the same city twice on a single trip, even though all outgoing connections are usable.

However, the Committee for Charging Cronerians (CCC), the organization responsible for setting the tolls on the toll route system, is greedy. At times, they might decide to add an integer amount to the cost of every single toll route. In order to trick Cronerians into thinking they are fair, the CCC might add a negative amount to the costs.

D days will pass. On the j^{th} day, Fax needs to deliver microwaves from city 1 to customers in city d_j and the CCC adds c_j moneys to the cost of every single toll route.

For each day, can you tell Fax the minimum amount of moneys he will need to spend to deliver the microwaves?

Input Specification

The first line of input will contain 3 space-separated integers, N (1 \le N \le 3\,000), M (1 \le M \le 6\,000), and D (1 \le D \le 2\times 10^6).

M lines of input follow. The i^{th} line will contain 3 space-separated integers, u_i , v_i, and t_i (1 \le u_i, v_i \le N; u_i \ne v_i; -10^9 \le t_i \le 10^9), specifying the i^{th} toll route.

D lines of input follow. The j^{th} line will contain 2 space-separated integers, c_j and d_j (1 \le d_j \le N). The absolute value of the total change from any toll route's initial cost will not exceed 10^9.

For 1 of the 15 points, each city has at most 1 out-going toll route and D \le 2\times 10^5.

For an additional 2 of the 15 points, N, M, D \le 100 and the cost of any toll route will always be non-negative.

For an additional 2 of the 15 points, N, M, D \le 30.

For an additional 2 of the 15 points, D \le 1\,000.

Output Specification

For each day, print the minimum amount of moneys Fax needs to spend to reach his destination. If no path exists, print Cannot Deliver.

Sample Input

5 6 3
1 2 2
2 5 4
1 5 10
1 3 2
3 4 3
4 5 4
0 5
10 5
-20 5

Sample Output

6
20
-21

Explanation for Sample Output

On the first day, no changes were made to the toll routes, so Fax should take the path 1\rightarrow 2 \rightarrow 5 for a minimal cost of 6.

On the second day, the cost of each toll route increased by 10, so Fax should take the path 1\rightarrow 5 for a minimal cost of 20.

On the third day, the cost of each toll route decreased by 20, so Fax should take the path 1\rightarrow 3\rightarrow 4\rightarrow 5 for a minimal cost of -21.


Comments

There are no comments at the moment.