Canadian Computing Competition: 2009 Stage 1, Senior #4
In Doubleclickland, there are ~N~ cities ~(2 \le N \le 5\,000)~, with each city having various trade routes to other cities. In total, there are ~T~ trade routes ~(1 \le T \le 5\,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) \le 10\,000~ and ~C(x, y) = C(y, x)~. Out of the ~N~ cities, ~K~ ~(1 \le K \le N)~ of these cities have stores with really nice pencils that can be purchased online. The price for each pencil in city ~x~ is ~P_x~ ~(0 \le P_x \le 10\,000)~.
Find the minimal price to purchase one pencil online and have it shipped to a particular city ~D~ ~(1 \le D \le 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.
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 online. The next ~K~ lines contain two integers, ~z~ and ~P_z~, to denote that the cost of a pencil in city ~z~ is ~P_z~. The last line contains the integer ~D~, the destination city.
Output the minimal total cost of purchasing a pencil online and shipping it to city ~D~.
3 3 1 2 4 2 3 2 1 3 3 3 1 14 2 8 3 3 1
CCC problem statements in large part from the PEG OJ