CCC '09 S4 - Shop and Ship

View as PDF

Submit solution

Points: 15
Time limit: 4.0s
Java 8 8.0s
Python 10.0s
Memory limit: 256M
Python 768M

Problem type

In Doubleclickland, there are N cities (N \le 5\,000), with each city having various trade routes to other cities. In total, there are T trade routes (0 \le T \le 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) \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 on-line. 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 on-line 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 on-line. The next K lines contains 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 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

CCC problem statements in large part from the PEG OJ


Comments


  • -4
    bloxblox  commented on Feb. 9, 2019, 5:51 p.m.

    this feels more like a 10 pointer idk


  • 1
    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
    root  commented on June 6, 2017, 8:49 p.m. edited

    ...wait a second. Since the maximum number of cities is 5000, then even if the map was a complete graph, it would have at most 12497500 edges. But the problem states that there are < 25000000 edges. How is this even possible?


    • 0
      anishmahto  commented on June 6, 2017, 10:22 p.m.

      Multiple edges between a single pair of cities probably.


      • 6
        root  commented on June 7, 2017, 11:57 a.m.

        I didn't handle multiple edges and I AC'd


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

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


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

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


  • 6
    cheesecake  commented on April 16, 2016, 4:15 p.m.

    Java 7 and 8 have been changed to 8s, normal time limit has been changed to 4s.


  • 2
    Cthulhu  commented on Feb. 8, 2016, 10:39 a.m.

    I noticed that my third last submission (I had been forgetting something rather vital for the others) was TLE-ing after the output had been printed. The print statement is the last statement in my code and is after all loops and the like. My accepted submission used the same general idea, but did not have this issue. What would have caused this to occur?


  • 1
    atarw  commented on Jan. 30, 2016, 2:20 p.m. edit 4

    I think my program is correct (and it gets a perfect score on PEG, clearing the last two test cases in 4s) but when I submit here it doesn’t seem to pass the last two test cases, even with a time limit two seconds higher :/

    Is there anything I’m doing wrong?

    Proof


  • 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.


    • 3
      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.


    • 0
      awaykened  commented on Nov. 1, 2015, 6:14 p.m. edit 3

      im dumb B-)


  • 3
    FatalEagle  commented on April 9, 2015, 7:27 p.m. edited

    Since the DMOJ recently started supporting custom time and memory limits for different languages, the following languages now have a separate limit:

    • PYPY2 (10s, 768MB)
    • PYPY3 (10s, 768MB)
    • JAVA (6s, 256MB)
    • JAVA8 (6s, 256MB)

    All other languages remain unaffected.


    • 0
      bobhob314  commented on April 10, 2015, 4:12 p.m. edit 5

      Hi Tim, just reporting a little bug.

      TLEs still report (>2.000s) instead of the custom time based on the language.

      Please see the image below.

      title

      Edit: If you're wondering why I'm still TLE'ing, remember that I am bobhob314


      • 4
        FatalEagle  commented on April 10, 2015, 10:10 p.m.

        Thanks, it's a known issue.


        • 8
          quantum  commented on April 10, 2015, 10:14 p.m.

          The current display is not wrong: the submission did run for more than 2 seconds.


          • 6
            kobortor  commented on April 10, 2015, 10:17 p.m.

            Technically correct, the best kind of correct.


      • 4
        sigkill  commented on April 10, 2015, 5:45 p.m. edit 5

        Doing big problems in Python is fun! I'm going to attempt this and maybe I'll corroborate your assertion.

        ED: If you look at the recent submissions, it seems quantum has already solved this in Python. So I guess your assertion isn't correct. I'm going to investigate anyhow.

        ED2: I have a small hint for you - hopefully I'm not out of line in writing it here. Nothing I write below really applies to the C/C++ solution(s) so I don't think it's a big spoiler.

        There are a few different ways of storing or representing a graph. This graph in particular can have many edges (up to O(n^2)), and your representation isn't really optimal for such a dense graph. You can implement the required algorithm with another structure that can be instantiated faster and has a smaller memory footprint (in this specific case).

        The particular graph representation you have chosen is generally applicable to most problems, but the advantages it yields disappear completely for very dense graphs such as this.

        Of course, this would all be a moot point if you were using C++ like a sane individual. For the sake of your own competitive success, I humbly suggest that you learn a faster language. :)

        ED3: Okay, having actually looked at your code now... there's some weird stuff happening. You aren't using the graph representation you mentioned in your comment - you are actually already using a structure similar to the one I'm alluding to. Use lists rather than dictionaries and see what happens.


  • 15
    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 _;
    

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

      Thank you so much :D


    • 0
      anishmahto  commented on Aug. 20, 2016, 2:19 p.m.

      Honestly though, for C++ scanf still works just fast enough. Worst time was 3.799s .


      • 2
        Xyene  commented on Aug. 20, 2016, 2:23 p.m.

        Our judges now are much faster than they were in 2014.


        • 0
          anishmahto  commented on Aug. 20, 2016, 2:31 p.m.

          Good point.


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

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


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

        it's a char named _