## CCC '09 S4 - Shop and Ship

View as PDF

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 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 online. The price for each pencil in city is .

Find the minimal price to purchase one pencil online 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 online. The next lines contain 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 online 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

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

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

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

• 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

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

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

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

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

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

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

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

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

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

Yes

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

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

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

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

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

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

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

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

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

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

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

Thank you so much :D

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

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

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

it's a char named _