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

CCC problem statements in large part from the PEG OJ


Comments


  • 7
    Jinx  commented on Dec. 22, 2021, 10:58 a.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


    • 2
      planT_444  commented on Jan. 1, 2022, 3:23 p.m.

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


  • -1
    Evang  commented on Oct. 13, 2020, 9:09 p.m.

    can a city have several prices for a pencil?


    • -2
      sushi  commented on Oct. 13, 2020, 9:34 p.m.

      It shouldn't matter.


  • 5
    alexzhang  commented on Nov. 21, 2018, 11:53 a.m.

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


  • 0
    septence123  commented on Dec. 18, 2016, 6:08 p.m.

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


    • 1
      Xyene  commented on Dec. 18, 2016, 7:08 p.m.

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


  • 0
    minecraftyugi  commented on Nov. 1, 2015, 4: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.


    • 2
      awaykened  commented on Nov. 1, 2015, 6:17 p.m.

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


      • 0
        minecraftyugi  commented on Nov. 1, 2015, 10:51 p.m.

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


  • 25
    FatalEagle  commented on Dec. 9, 2014, 10:17 a.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 _;
    

    • 2
      1419903188  commented on Nov. 9, 2017, 6:47 p.m.

      Thank you so much :D


    • 1
      zys5945  commented on Nov. 27, 2015, 12:18 p.m. edited

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


      • 16
        kobortor  commented on Nov. 27, 2015, 2:21 p.m.

        it's a char named _