CCC '09 S4 - Shop and Ship

View as PDF
Submit solution
Points: 10
Time limit: 2.0s
Java 3.0s
Python 5.0s
Memory limit: 256M
Python 768M
Problem type
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.

Input Specification

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 Specification

Output the minimal total cost of purchasing a pencil online 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

Comments


  • 0
    N1skk  commented on Dec. 23, 2023, 12:18 a.m.

    Is it guaranteed that there is only 1 undirected trade route between 2 cities?


  • 2
    maxcruickshanks  commented on June 11, 2022, 4:01 a.m.

    Since the original data were weak, an additional test case was added, and all submissions were rejudged.


  • 13
    Jinx  commented on Dec. 22, 2021, 3:58 p.m. ← edited

    So... you're telling me I have to pay up to $10000 for a pencil. And then pay to get it shipped. And then wait for it to be shipped across potentially thousands of cities.

    ... no thanks


    • 5
      planT_444  commented on Jan. 1, 2022, 8:23 p.m.

      how good would a "really nice pencil" have to be to cost that much


  • -5
    Evang  commented on Oct. 14, 2020, 1:09 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -10
      sushi  commented on Oct. 14, 2020, 1:34 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • 8
    alexzhang  commented on Nov. 21, 2018, 4:53 p.m.

    Is it guaranteed that it is possible to successfully ship a pencil to your city?


  • -3
    septence123  commented on Dec. 18, 2016, 11:08 p.m.

    Is my algorithm too slow or a problem with the judge?


    • 3
      Xyene  commented on Dec. 19, 2016, 12:08 a.m.

      Your algorithm is suboptimal, and this problem is particularly strict with time limits.


  • 1
    minecraftyugi  commented on Nov. 1, 2015, 9:13 p.m.

    What's the fastest way to store all the input in Python? I am TLEing even before i get all the trade routes processed on cases 4 and 5. I've tried using both lists and dictionaries, but they aren't working fast enough.


    • 3
      awaykened  commented on Nov. 1, 2015, 11:17 p.m.

      otherwise, storing the graph in an adjacency matrix represented by python lists should be fine


      • 0
        minecraftyugi  commented on Nov. 2, 2015, 3:51 a.m.

        Thanks a lot. Using dictionaries is a lot slower for some reason.


  • 29
    FatalEagle  commented on Dec. 9, 2014, 3:17 p.m.

    Fast input is required for this problem.

    Here is a macro for C++ that reads an unsigned integer much faster than scanf:

    #define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;

    • 3
      1419903188  commented on Nov. 9, 2017, 11:47 p.m.

      Thank you so much :D


    • 3
      zys5945  commented on Nov. 27, 2015, 5:18 p.m. ← edited

      How does that work? Is there any special meaning to the "char _;"?


      • 19
        kobortor  commented on Nov. 27, 2015, 7:21 p.m.

        it's a char named _