### 2011 Canadian Computing Competition, Stage 2

## Day 1, Problem 2: Vampire Tunnels

You are a vampire, and you want to travel from some point `A` to
another point `B`. You may travel in the sunshine above ground or avoid
the sunshine by travelling 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` seconds in total, you want to
minimize the total travel time (given that you have a constant speed of 1 unit
of distance per second).

### Input Format

On the first line of input, you have the number `S`
(0 ≤ `S` ≤ 3600), the maximum number of
seconds that you can be exposed to the sun. On the next line is the number
`N` (2 ≤ `N` ≤ 1600), which is the
number of points, and the number `E`
(1 ≤ `E` ≤ 10000), which is the number of
connections between these `N` points, separated by one space.

The next `E` lines each contain information about the connections
between points. Specifically, each of these lines contains four integers:
`s` (0 ≤ `s` ≤ `N`-1), one
end point of a connection; `t`
(0 ≤ `t` ≤ `N`-1,
`s` ≠ `t`), the other end point of a connection;
`d` (1 ≤ `d` ≤ 10000), the distance
between `s` and `t`; and `u`, which is 1 if this
connection is above ground and 0 if it is underground.

Note: for 30% of the marks for this question, you can assume
`N` ≤ 50.

### Output Format

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

### Sample Input

3 4 6 0 1 3 1 0 2 4 1 0 3 10 1 1 2 3 0 1 3 1 1 2 3 3 0

### Sample Output

9

### Explanation

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

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 256M

**Added:** Jun 05, 2011

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

bbi5291on Feb 11, 2012 - 9:18:09 pm UTC lolDanielon Jun 05, 2011 - 11:38:57 pm UTC Bad testcases?bbi5291on Jun 06, 2011 - 12:03:48 am UTC Re: Bad testcases?bbi5291on Jun 06, 2011 - 12:39:37 am UTC Re: Bad testcases?