VM7WC '15 #4 Gold - Chain Rule - Olympiads Online Judge

VM7WC '15 #4 Gold - Chain Rule

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 2.5s

Memory limit: 256M

Author:

thorthugnasty

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 $N$ ~N~ $(2 \le N \le 100\,000)$ ~(2 \le N \le 100\,000)~ cities, numbered $0 \dots N-1$ ~0 \dots N-1~ and $M$ ~M~ $(1 \le M \le 300\,000)$ ~(1 \le M \le 300\,000)~ highways. Phillips Exeter Academy, where Melanie starts, is located in city $0$ ~0~ and Washington, D.C. is city $N-1$ ~N-1~. The $i^\text{th}$ ~i^\text{th}~ $(1 \le i \le M)$ ~(1 \le i \le M)~ highway connects cities $A_i$ ~A_i~ and $B_i$ ~B_i~ $(0 \le A_i, B_i \le N-1)$ ~(0 \le A_i, B_i \le N-1)~, takes $t_i$ ~t_i~ $(1 \le t_i \le 10\,000)$ ~(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$ ~0~ or $N-1$ ~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.

Hint: Learn Dijkstra's algorithm.

Input Specification

The first line of input contains two space-separated integers, $N$ ~N~ and $M$ ~M~.

The next $M$ ~M~ lines contain three space separated integers, $A_i$ ~A_i~, $B_i$ ~B_i~, and $t_i$ ~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

Sample Output

Explanation

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

Comments

0

Evanhyd commented on Jan. 15, 2021, 9:42 p.m. ← edited →

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

0

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

For $N=2$ ~N=2~, where would Alex live?

0

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

Note that Alex may also live in city $0$ ~0~ or $N-1$ ~N-1~, in which case Melanie does not need to go out of her way.

-2

Leon 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?

-2

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

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

0

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

Using a priority queue right?

0

omaewamoushindeiru 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 ;)

2

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

0

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

Will all cities be, directly or indirectly, connected?

0

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

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

2

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

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

3

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

No.

26

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

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

4

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

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