## CCC '15 S4 - Convex Hull

View as PDF

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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### 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 centimetres thick. The archipelago has islands, numbered from to . There are sea routes amongst them, where the route runs directly between two different islands and ; (), takes minutes to travel along in either direction, and has rocks that wear down the ship's hull by centimetres. There may be multiple routes running between a pair of islands.

You would like to travel from island to a different island () along a sequence of sea routes, such that your ship's hull remains intact – in other words, such that the sum of the routes' values is strictly less than .

Additionally, you are in a hurry, so you would like to minimize the amount of time necessary to reach island from island . It may not be possible to reach island from island , 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 , and (), each separated by one space.

The next lines each contain integers , , and (), each separated by one space. The line in this set of lines describes the sea route (which runs from island to island , takes minutes and wears down the ship's hull by centimetres). Notice that (that is, the ends of a sea route are distinct islands).

The last line of input contains two integers and (), the islands between which we want to travel.

For 20% of marks for this question, and . For another 20% of the marks for this problem, and .

#### Output Specification

Output a single integer: the integer representing the minimal time required to travel from to without wearing out the ship's hull, or -1 to indicate that there is no way to travel from to 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

#### Output for Sample Input 1

7

#### Explanation of Output for Sample Input 1

The path of length from to would wear out the hull of the ship. The three paths of length ( and two different ways) take at least minutes. The path takes minutes and only wears down the hull by centimetres, whereas the path takes minutes and wears down the hull by centimetres.

#### Sample Input 2

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

#### Output for Sample Input 2

-1

#### Explanation of Output for Sample Input 2

The direct path wears down the hull to , as does the path .

• commented on Nov. 17, 2020, 10:51 a.m. edited

Can someone explain to me why my code using Dijktra fails testcase 3, but SPFA passes?

• commented on March 13, 2020, 8:03 p.m.

My code passes all cases but test case 6. Anybody know why?

• commented on Jan. 27, 2021, 4:36 p.m.

• commented on May 28, 2019, 9:59 a.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on May 28, 2019, 1:36 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Dec. 7, 2017, 12:27 p.m. edited

Why do I keep getting test cases 5 and 6 wrong? Extremely frustrating!

• commented on Dec. 7, 2017, 6:54 p.m.

Your solution seems not correct. I'm surprised it can pass so many cases. You can test your solution with this case.

6 4 4
1 2 2 2
2 3 1 2
1 3 5 3
3 4 1 2
1 4
• commented on June 12, 2020, 8:04 p.m. edited

Umm could someone please look at my code and see what is wrong with it? I am getting RTE but it works fine on my computer Edit I got the data set and ran it on my computer and everything was correct... sooooo any help??

• commented on June 12, 2020, 9:56 p.m.

Perhaps you are using too much memory? Your 2000 x 2000 array of int queue pairs looks extremely costly. Consider another way to compress the information, such as an adjacency list.

• commented on June 14, 2020, 1:37 p.m.

But the memory limit is 512 and the compiler clearly says that I am only using 240ish MB.

• commented on June 14, 2020, 2:13 p.m.

std::bad_alloc is thrown before the memory is allocated, so the 240MB usage is before the memory allocation that caused it to go past the memory limit.

• commented on March 13, 2020, 6:52 p.m.