CCO '11 P2 - Vampire Tunnels - Olympiads Online Judge

CCO '11 P2 - Vampire Tunnels

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.4s

Memory limit: 1G

Problem type

Canadian Computing Competition: 2011 Stage 2, Day 1, Problem 2

You are a vampire, and you want to travel from some point $A$ $A$ to another point $B$ $B$ . You may travel in the sunshine above ground or avoid the sunshine by traveling underground via certain tunnels. You have mapped out the area you wish to travel, and have found some secret tunnels between some points, some other points that you can walk between above ground. Both the tunnels and above ground paths are bidirectional. Given that you can't be exposed to the sunlight for more than $S$ $S$ seconds in total $(0 \le S \le 3\,600)$ $(0 \leq S \leq 3 600)$ , you want to minimize the total travel time (given that you have a constant velocity of $1$ $1$ unit of distance per second).

Input Specification

On the first line of input, you have the number $S$ $S$ , the maximum number of seconds that you can be exposed to the sun. On the next line is the number $N$ $N$ $(2 \le N \le 1\,600)$ $(2 \leq N \leq 1 600)$ , which is the number of points, and the number $E$ $E$ $(1 \le E \le 10\,000)$ $(1 \leq E \leq 10 000)$ , which is the number of connections between these $N$ $N$ points, separated by one space.

The next $E$ $E$ lines each contain information about the connections between points. Specifically, each of these lines contain four integers: $s$ $s$ (one end point of a connection) $(0 \le s \le N - 1)$ $(0 \leq s \leq N - 1)$ , $t$ $t$ (the other end point of a connection) $(0 \le t \le N - 1, s \ne t)$ $(0 \leq t \leq N - 1, s \neq t)$ , $d$ $d$ (the distance between $s$ $s$ and $t$ $t$ , $1 \le d \le 10\,000$ $1 \leq d \leq 10 000$ ), $u$ $u$ (indicate whether this is underground or above ground: $1$ $1$ indicates it is above ground, and $0$ $0$ indicates there is a tunnel between $s$ $s$ and $t$ $t$ ).

Note: for $30\%$ $30 %$ of the marks for this question, you can assume $N \le 50$ $N \leq 50$ .

Output Specification

The output is one integer, which is the minimum amount of time required to get from point $0$ $0$ to point $N - 1$ $N - 1$ , with the constraint that there are not more than $S$ $S$ seconds of exposure to the sun. If there is no possible path which satisfies the constraint, output $-1$ $- 1$ .

Sample Input

Copy

Sample Output

Copy

Explanation for Sample Output

The path $0 \to 1 \to 2 \to 3$ $0 \to 1 \to 2 \to 3$ gives a total travel time of $9$ $9$ seconds with $3$ $3$ seconds of exposure to the sun. All other paths either required more time (e.g., $0 \to 3$ $0 \to 3$ uses $10$ $10$ seconds) or overexpose to the sun (e.g., $0 \to 1 \to 3$ $0 \to 1 \to 3$ exposes to the sun for $4$ $4$ seconds).

Comments

0

rnpmat08_v2 commented 95 days ago

Note that you can't be exposed to the sunlight for MORE THAN $S$ $S$ seconds; if you are exposed for exactly $S$ $S$ seconds you will be fine.

9

aeternalis1 commented on Aug. 11, 2017, 6:54 p.m.

Lower memory usage in python

I AC all test cases except number 6, which I MLE by a somewhat small margin. Is there any way to make my code use less memory?