Mock CCO '18 Contest 4 Problem 3 - Counterattack

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.3s
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 will contain 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


  • 8
    dxke02  commented on Jan. 15, 2021, 6:13 p.m.

    don't know if this was intended but submitted a correct answer to https://dmoj.ca/problem/cco12p2 then copied and pasted the same answer to this and still passed