VM7WC '15 #4 Gold - Chain Rule

View as PDF

Submit solution

Points: 10
Time limit: 2.5s
Memory limit: 256M

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

Melanie, a student at Phillips Exeter Academy has discovered a new theorem regarding relative velocities, which she calls the Chain Rule. Now she must drive to Washington, D.C. to show her groundbreaking results to the president.

The world she lives in is made up of N (2 \le N \le 100\,000) cities, numbered 0 \dots N-1 and M (1 \le M \le 300\,000) highways. Phillips Exeter Academy, where Melanie starts, is located in city 0 and Washington, D.C. is city N-1. The i^{th} (1 \le i \le M) highway connects cities A_i and B_i (0 \le A_i, B_i \le N-1), takes t_i (1 \le t_i \le 10\,000) minutes to travel on, and can be taken in either direction.

However, Melanie must first visit her rival, Alex Song, to brag about her results. Unfortunately, Melanie has no idea which city Alex actually lives in. Regardless of which city Alex lives in, Melanie wants to travel from Phillips Exeter to Alex's house then to Washington, D.C. in the minimum amount of time possible. Knowing that Alex's house may be extremely inconveniently located, Melanie wants to determine how long of a trip she may need in the worst case. You must consider all possible locations of Alex's house, then determine the longest time that Melanie may need to complete her trip, given that she always takes the fastest route from Phillips Exeter to Alex's house then to Washington, D.C.

Note that Alex may also live in city 0 or N-1, in which case Melanie does not need to go out of her way. Also note that Melanie is allowed to pass through Washington, D.C. on her way to Alex's house, however she must still make the journey from Alex's house back to Washington. There will always exist a path between any two cities.


Learn Dijkstra's algorithm: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Input Specification

The first line of input contains two space-separated integers, N and M. The next M lines contain three space separated integers, A_i, B_i, and t_i.

Output Specification

Print a single integer, the maximum amount of time that Melanie may need to travel from Exeter to Alex's house to Washington, D.C., given that she always takes the optimal route.

Sample Input

5 5
0 1 5
1 2 4
0 3 8
2 3 2
4 2 3

Sample Output



If Alex lives in city 3, the shortest path from 0 to 3 would take 8 minutes, and the shortest path from 3 to 4 would take 5 minutes. Thus the trip will take 8 + 5 = 13 minutes. If Alex lived anywhere else, the shortest trip would take 12 minutes. Therefore, the longest trip Melanie may be required to take will take 13 minutes.


  • 0
    Leon  commented on June 24, 2017, 9:37 p.m. edited

    Can someone please give me a hint on what I'm doing wrong? Do I just need to optimize or is my whole idea wrong?

    • 0
      Kirito  commented on June 24, 2017, 11:01 p.m.

      Your Dijkstra's runs in \mathcal O(N^2), which TLEs. There's another variant of Dijkstra's which runs in \mathcal O(E \log V)

      • 0
        idkanything  commented on Dec. 25, 2018, 12:31 p.m.

        Using a priority queue right?

        • 1
          BMP  commented on Dec. 26, 2018, 3:18 p.m.

          you can do it with a normal queue as well, just don't use an adjacency matrix ;)

  • 1
    println_hi_  commented on Oct. 30, 2016, 12:30 a.m. edited

    In python I feel like I have created the fastest algorithm I can think of. However I am failing with TLE on the last two test cases. Could I have a hint on how to proceed?

    EDIT:I had too do two things to AC. One was a way of optimising my dijkstra's by a constant factor. The other was removing my comments, the latter presumably worked because python is an interpreted language.

  • 1
    println_hi_  commented on Oct. 29, 2016, 10:28 a.m.

    Will all cities be, directly or indirectly, connected?

    • 0
      chenj  commented on Oct. 29, 2016, 11:46 a.m.

      "There will always exist a path between any two cities."

  • 0
    JeffreyZ  commented on May 13, 2015, 10:40 a.m.

    Where did the submissions go?

    • 0
      awaykened  commented on May 13, 2015, 10:58 a.m.

      are you perhaps trying to view this problem while in a contest?

  • 0
    thorthugnasty  commented on Jan. 29, 2015, 11:36 p.m.

    Time limit is changed to 5s; all solutions rejudged.

  • 3
    bobhob314  commented on Jan. 29, 2015, 3:18 p.m.

    Will there be more than one highway between two identical cities?

  • 22
    bobhob314  commented on Jan. 29, 2015, 3:07 p.m.

    So you're saying that Melanie needs to "exeter" home to travel to Washington?

    • 2
      JeffreyZ  commented on Jan. 29, 2015, 3:49 p.m.

      Please stop making me laugh, I'm trying to do the question