CCC '15 S4 - Convex Hull

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 5.0s
Memory limit: 512M

Problem type
Canadian Computing Competition: 2015 Stage 1, Senior #4

You are travelling on a ship in an archipelago. The ship has a convex hull which is K centimeters 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_i; (1 \le a_i, b_i \le N), takes t_i minutes to travel along in either direction, and has rocks that wear down the ship's hull by h_i centimetres. There may be multiple routes running between a pair of islands.

You would like to travel from island A to a different island B (1 \le A, B \le 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 Specification

The first line of input contains three integers K, N and M (1 \le K \le 200, 2 \le N \le 2 000, 1 \le M \le 10 000), each separated by one space.

The next M lines each contain 4 integers a_i, b_i, t_i and h_i (1 \le a_i, b_i \le N, 1 \le t_i \le 10^5, 0 \le h_i \le 200), each separated by one space. The i^{th} line in this set of M lines describes the i^{th} sea route (which runs from island a_i to island b_i, takes t_i minutes and wears down the ship's hull by h_i centimetres). Notice that a_i \ne b_i (that is, the ends of a sea route are distinct islands).

The last line of input contains two integers A and B (1 \le A, B \le N; A \ne B), the islands between which we want to travel.

For 20% of marks for this question, K=1 and N \le 200. For another 20% of the marks for this problem, K = 1 and N \le 2 000.

Output Specification

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 Bwithout 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


Sample 1 Explanation

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 5 minutes but wear down the hull too much. 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 10 minutes and wears down the hull by 10 centimetres.

Sample Input 2

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

Sample Output 2


Sample 2 Explanation

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


There are no comments at the moment.