### 2015 Canadian Computing Competition, Stage 1

## Problem S4: Convex Hull

You are travelling on a ship in an archipelago. The ship has a convex hull which is `K` centimetres thick. The archipelago has `N` islands, numbered from 1 to `N`. There are `M` sea routes amongst them, where the `i`-th route runs directly between two different islands `a _{i}` and

`b`(1 ≤

_{i}`a`,

_{i}`b`≤

_{i}`N`), takes

`t`minutes to travel along in either direction, and has rocks that wear down the ship's hull by

_{i}`h`centimetres. There may be multiple routes running between a pair of islands.

_{i}You would like to travel from island `A` to a different island `B` (1 ≤ `A`, `B` ≤ `N`) along a sequence of sea routes, such that your ship's hull remains intact – in other words, such that the sum of the routes' `h _{i}` values is strictly less than

`K`.

Additionally, you are in a hurry, so you would like to minimize the amount of time necessary to reach island `B` from island `A`. It may not be possible to reach island `B` from island `A`, however either due to insufficient sea routes or the having the ship's hull wear out.

### Input

The first line of input contains three integers `K`, `N` and `M` (1 ≤ `K` ≤ 200; 2 ≤ `N` ≤ 2000; 1 ≤ `M` ≤ 10000), each separated by one space.

The next `M` lines each contain 4 integers `a _{i}`

`b`

_{i}`t`

_{i}`h`(1 ≤

_{i}`a`,

_{i}`b`≤

_{i}`N`; 1 ≤

`t`≤ 10

_{i}^{5}; 0 ≤

`h`≤ 200), each separated by one space. The

_{i}`i`-th line in this set of

`M`lines describes the

`i`-th sea route (which runs from island

`a`to island

_{i}`b`, takes

_{i}`t`minutes and wears down the ship's hull by

_{i}`h`centimetres). Notice that

_{i}`a`≠

_{i}`b`(that is, the ends of a sea route are distinct islands).

_{i}The last line of input contains two integers `A` and `B` (1 ≤ `A`, `B` ≤ `N`; `A` ≠ `B`), the islands between which we want to travel.

For 20% of marks for this question, `K` = 1 and `N` ≤ 200. For another 20% of the marks for this problem, `K` = 1 and `N` ≤ 2000.

### Output

Output a single integer: the integer representing the minimal time required to travel from `A` to `B` without wearing out the ship's hull, or `-1`

to indicate that there is no way to travel from `A` to `B` without wearing out the ship's hull.

### Sample Input 1

10 4 7 1 2 4 4 1 3 7 2 3 1 8 1 3 2 2 2 4 2 1 6 3 4 1 1 1 4 6 12 1 4

### Sample Output 1

7

### Explanation of Sample 1

The path of length 1 from 1 to 4 would wear out the hull of the ship. The three paths of length 2 ([1, 2, 4] and [1, 3, 4] two different ways) take at least 8 minutes. The path [1, 2, 3, 4] takes 7 minutes and only wears down the hull by 7 centimetres, whereas the path [1, 3, 2, 4] takes 13 minutes and wears down the hull by 5 centimetres.

### Sample Input 2

3 3 3 1 2 5 1 3 2 8 2 1 3 1 3 1 3

### Sample Output 2

-1

### Explanation of Sample 2

The direct path [1, 3] wears down the hull to 0, as does the path [1, 2, 3].

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 256M

**Added:** Feb 21, 2015

**Author:** SourSpinach

**Languages Allowed:**

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

## Comments (Search)

P234reron Feb 24, 2017 - 3:20:05 pm UTC ErrorThanks

jargonon Feb 24, 2017 - 8:07:39 pm UTC Re: ErrorP234reron Feb 24, 2017 - 9:31:26 pm UTC Re: Errorgpfaulton Jan 31, 2017 - 8:04:14 pm UTC Weak test cases3 3 4

1 2 3 0

1 2 2 1

1 2 1 2

2 3 1 1

1 3

Correct output:

3

kobortoron Jan 31, 2017 - 8:34:52 pm UTC Re: Weak test caseslolzballson Feb 24, 2015 - 2:02:02 am UTC UndirectedThe problem text states that " ... i-th sea route (which runs from island ai to island bi ... ", implying that the graph that represents this is directed, rather than undirected, as according to the explanation.

Is the graph directed or not?

Butaneon Feb 24, 2015 - 2:34:50 am UTC Re: Undirected