2009 Canadian Computing Competition, Stage 1

Problem S4: Shop and Ship

In Doubleclickland, there are N cities (N ≤ 5,000), with each city having various trade routes to other cities. In total, there are T trade routes (0 ≤ T ≤ 25,000,000). in Doubleclickland. For each trade route between two cities x and y, there is a transportation cost C(x; y) to ship between the cities, where C(x, y) > 0, C(x, y) ≤ 10,000 and C(x, y) = C(y, x). Out of the N cities, K (1 ≤ K ≤ N) of these cities have stores with really nice pencils that can be purchased on-line. The price for each pencil in city x is Px (0 ≤ Px ≤ 10,000).

Find the minimal price to purchase one pencil on-line and have it shipped to a particular city D (1 ≤ D ≤ N) using the cheapest possible trade-route sequence. Notice that it is possible to purchase the pencil in city D and thus require no shipping charges.

Input

The first line of input contains N, the number of cities. You can assume the cities are numbered from 1 to N. The second line of input contains T, the number of trade routes. The next T lines each contain 3 integers, x y C(x, y), to denote the cost of using the trade route between cities x and y is C(x, y). The next line contains the integer K, the number of cities with a store that sells really nice pencils on-line. The next K lines contains two integers, z and Pz, to denote that the cost of a pencil in city z is Pz. The last line contains the integer D, the destination city.

Output

Output the minimal total cost of purchasing a pencil on-line and shipping it to city D.

Sample Input

3
3
1 2 4
2 3 2
1 3 3
3
1 14
2 8
3 3
1

Sample Output

6

All Submissions
Best Solutions


Point Value: 15
Time Limit: 5.00s
Memory Limit: 256M
Added: May 11, 2009

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

Comments (Search)

How come solutions that didn't meet the runtime requirement were accepted?

the time limit is per test case

Test case 1 has some cities that are numbered N+1 which does not satisfy the problem's constraints.

Sorry for the inconvenience. This has been fixed, and all affected solutions were rejudged.

mem limit 1024MB XDD

data not fully updated yet... but who cares anyway xD

When Hanson submitted my solution I got 0/50 but when I submit the same solution I get 10/50?

The CCC official data had a bug in it, but your program passes that case now. (You'll get 3 more points!)