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

#### 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

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?

Edit: Using set instead of a priority queue worked.

can a city have several prices for a pencil?

It shouldn't matter.

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

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

Yes

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

Multiple edges between a single pair of cities probably.

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

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

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

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

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?

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

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.

otherwise, storing the graph in an adjacency matrix represented by python

listsshould be fineThanks a lot. Using dictionaries is a lot slower for some reason.

im dumb B-)

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

All other languages remain unaffected.

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.

Edit:If you're wondering why I'm still TLE'ing, remember that I am bobhob314Thanks, it's a known issue.

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

Technically correct, the best kind of correct.

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.

Fast input is required for this problem.

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

Thank you so much :D

Honestly though, for C++ scanf still works

justfast enough. Worst time was 3.799s .Our judges now are much faster than they were in 2014.

Good point.

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

it's a char named _