## VM7WC '15 #4 Gold - Chain Rule

View as PDF

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

Author:
Problem type

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 cities, numbered and highways. Phillips Exeter Academy, where Melanie starts, is located in city and Washington, D.C. is city . The highway connects cities and , takes 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 or , 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.

Hint: Learn Dijkstra's algorithm.

#### Input Specification

The first line of input contains two space-separated integers, and .

The next lines contain three space separated integers, , , and .

#### 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.

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

13

#### Explanation

If Alex lives in city , the shortest path from to would take minutes, and the shortest path from to would take minutes. Thus the trip will take minutes. If Alex lived anywhere else, the shortest trip would take minutes. Therefore, the longest trip Melanie may be required to take will take minutes.

• commented on Jan. 15, 2021, 9:42 p.m.

My custom linked list doesn't work, but the priority queue is fine. I guess it is related to the insertion time complexity? (O(N) vs O(log(N))

• commented on Jan. 15, 2021, 2:23 a.m.

For , where would Alex live?

• commented on Jan. 15, 2021, 8:16 p.m.

Note that Alex may also live in city or , in which case Melanie does not need to go out of her way.

• commented on June 25, 2017, 1:37 a.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?

• commented on June 25, 2017, 3:01 a.m.

Your Dijkstra's runs in , which TLEs. There's another variant of Dijkstra's which runs in

• commented on Dec. 25, 2018, 5:31 p.m.

Using a priority queue right?

• commented on Dec. 26, 2018, 8:18 p.m.

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

• commented on Oct. 30, 2016, 4: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.

• commented on Oct. 29, 2016, 2:28 p.m.

Will all cities be, directly or indirectly, connected?

• commented on Oct. 29, 2016, 3:46 p.m.

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

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

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

• commented on Jan. 29, 2015, 10:11 p.m.

No.

• commented on Jan. 29, 2015, 8:07 p.m.

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

• commented on Jan. 29, 2015, 8:49 p.m.

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