CCC '15 S4 - Convex Hull

View as PDF

Submit solution


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

Output for Sample Input 1

7

Explanation of Output for Sample Input 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

Output for Sample Input 2

-1

Explanation of Output for Sample Input 2

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


Comments


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

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


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

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


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

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


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

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


    • 58
      bruce  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

      • 3
        d3story  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??


        • 6
          BreadTurtle  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.


          • 3
            d3story  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.


            • 8
              Ninjaclasher  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.


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

        Is the answer 6?


        • 4
          Kevy3030  commented on April 17, 2020, 11:18 a.m.

          Appears so.