Mock CCO '18 Contest 4 Problem 3 - Counterattack

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 0.5s
Memory limit: 64M

Problem type

The Zerg, having held off the Protoss timing attack, is preparing to counterattack! However, they don't wish to be all that obvious, so they will not take the shortest path to the Protoss natural to counterattack. Instead, they will take the second-shortest path! It is guaranteed there are at least two paths with distinct lengths.

To be clear about what this means, we model the map the Zerg is on as an undirected weighted graph. Let L_1 be the length of the shortest path from vertex 1 to vertex N. The Zerg is looking for the smallest realizable path length L_2 > L_1. The Zerg army must start at vertex 1 and end up at vertex N, only traveling along edges in the graph. The Zerg army must traverse an edge in its entirety, but is allowed to visit vertices more than once or reuse edges.

Constraints

2 \le N \le 5 \cdot 10^3

1 \le M \le 10^5

1 \le A_i, B_i \le N

1 \le W_i \le 5 \cdot 10^3

Input Specification

The first line will contain two integers, N and M.

Each of the next M lines contains three space-separated integers, A_i, B_i and W_i, indicating there is an undirected edge between vertices A_i and B_i with length W_i.

Output Specification

Output the length of the second-shortest path.

Sample Input

4 4
1 2 100
2 4 200
2 3 250
3 4 100

Sample Output

450

Comments

There are no comments at the moment.