CCC '09 S4 - Shop and Ship - DMOJ: Modern Online Judge

CCC '09 S4 - Shop and Ship

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

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$ $N$ cities $(2 \le N \le 5\,000)$ $(2 \leq N \leq 5 000)$ , with each city having various trade routes to other cities. In total, there are $T$ $T$ trade routes $(1 \le T \le 5\,000\,000)$ $(1 \leq T \leq 5 000 000)$ in Doubleclickland. For each trade route between two cities $x$ $x$ and $y$ $y$ , there is a transportation cost $C(x, y)$ $C (x, y)$ to ship between the cities, where $C(x, y) > 0$ $C (x, y) > 0$ , $C(x, y) \le 10\,000$ $C (x, y) \leq 10 000$ and $C(x, y) = C(y, x)$ $C (x, y) = C (y, x)$ . Out of the $N$ $N$ cities, $K$ $K$ $(1 \le K \le N)$ $(1 \leq K \leq N)$ of these cities have stores with really nice pencils that can be purchased online. The price for each pencil in city $x$ $x$ is $P_x$ $P_{x}$ $(0 \le P_x \le 10\,000)$ $(0 \leq P_{x} \leq 10 000)$ .

Find the minimal price to purchase one pencil online and have it shipped to a particular city $D$ $D$ $(1 \le D \le N)$ $(1 \leq D \leq N)$ using the cheapest possible trade-route sequence. Notice that it is possible to purchase the pencil in city $D$ $D$ and thus require no shipping charges.

Input Specification

The first line of input contains $N$ $N$ , the number of cities. You can assume the cities are numbered from $1$ $1$ to $N$ $N$ . The second line of input contains $T$ $T$ , the number of trade routes. The next $T$ $T$ lines each contain 3 integers, $x$ $x$ , $y$ $y$ , $C(x,y)$ $C (x, y)$ , to denote the cost of using the trade route between cities $x$ $x$ and $y$ $y$ is $C(x, y)$ $C (x, y)$ . The next line contains the integer $K$ $K$ , the number of cities with a store that sells really nice pencils online. The next $K$ $K$ lines contain two integers, $z$ $z$ and $P_z$ $P_{z}$ , to denote that the cost of a pencil in city $z$ $z$ is $P_z$ $P_{z}$ . The last line contains the integer $D$ $D$ , the destination city.

Output Specification

Output the minimal total cost of purchasing a pencil online and shipping it to city $D$ $D$ .

Sample Input

Copy

Sample Output

Copy

Comments

1

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

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

1

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

13

Jinx 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

5

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

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

-5

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

can a city have several prices for a pencil?

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

-11

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

It shouldn't matter.

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

9

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

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

6

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

Yes

-3

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

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

3

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

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

1

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

3

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

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

0

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

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

29
FatalEagle 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:

Copy
#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, 11:47 p.m.

Thank you so much :D

3

zys5945 commented on Nov. 27, 2015, 5:18 p.m. ← edited →

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

19

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

it's a char named _