CCC '09 S4 - Shop and Ship

View as PDF

Points: 15
Time limit: 2.0s
Java 3.0s
Python 5.0s
Memory limit: 256M
Python 768M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2009 Stage 1, Senior #4

In Doubleclickland, there are cities , with each city having various trade routes to other cities. In total, there are trade routes . in Doubleclickland. For each trade route between two cities and , there is a transportation cost to ship between the cities, where , and . Out of the cities, of these cities have stores with really nice pencils that can be purchased on-line. The price for each pencil in city is .

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

Input Specification

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

Output Specification

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

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

• commented on Nov. 23, 2020, 8:30 p.m.

The Official CEMC test data only has a maximum of 5000000 edges, why would they say that the maximum was 25000000 edges in the problem statement?

• commented on Oct. 31, 2020, 6:24 p.m. edited

Edit: Using set instead of a priority queue worked.

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

can a city have several prices for a pencil?

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

It shouldn't matter.

• commented on June 19, 2020, 6:14 p.m.

It may be helpful to know that there is actually a maximum of 5,000,000 trade routes, not 25,000,000.

• commented on Feb. 9, 2019, 5:51 p.m. edited

This comment is hidden due to too much negative feedback. Click here to view it.

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

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

• commented on Nov. 21, 2018, 1:23 p.m.

Yes

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

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

Multiple edges between a single pair of cities probably.

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

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

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

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

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

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

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

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

• 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

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

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

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

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

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

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

im dumb B-)

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

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

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

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

Thanks, it's a known issue.

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

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

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

Technically correct, the best kind of correct.

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

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

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

Thank you so much :D

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

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

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

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

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

Good point.

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

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

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

it's a char named _