CCO '12 P2 - The Hungary Games

View as PDF

Submit solution

Points: 15
Time limit: 1.0s
Memory limit: 1G

Problem type
Canadian Computing Competition: 2012 Stage 2, Day 1, Problem 2

Welcome to the Hungary Games! The streets of Budapest form a twisted network of one-way streets. You have been forced to join a race as part of a "Reality TV" show where you race through these streets, starting at the Szechenyi thermal bath (s for short) and ending at the Tomb of Gul Baba (t for short).

Naturally, you want to complete the race as quickly as possible, because you will get more promotional contracts the better you perform. However, there is a catch: any person who is smart enough to take a shortest s-t route will be thrown into the Palvolgyi cave system and kept as a national treasure. You would like to avoid this fate, but still be as fast as possible. Write a program that computes a strictly-second-shortest s-t route.

Sometimes the strictly second-shortest route visits some nodes more than once; see Sample Input 2 for an example.

Input Specification

The first line will have the format N M, where N is the number of nodes in Budapest and M is the number of edges. The nodes are 1, 2, \dots, N; node 1 represents s; node N represents t. Then there are M lines of the form A B L, indicating a one-way street from A to B of length L. You can assume that A \ne B on these lines, and that the ordered pairs (A, B) are distinct.

Output Specification

Output the length of a strictly-second-shortest route from s to t. If there are less than two possible lengths for routes from s to t, output -1.

Limits

Every length L will be a positive integer between 1 and 10\,000. For 50% of the test cases, we will have 2 \le N \le 40 and 0 \le M \le 1000. All test cases will have 2 \le N \le 20\,000 and 0 \le M \le 100\,000.

Sample Input 1

4 6
1 2 5
1 3 5
2 3 1
2 4 5
3 4 5
1 4 13

Output for Sample Input 1

11

Explanation for Sample Output 1

There are two shortest routes of length 10 (1 \to 2 \to 4, 1 \to 3 \to 4) and the strictly-second-shortest route is 1 \to 2 \to 3 \to 4 with length 11.

Sample Input 2

2 2
1 2 1
2 1 1

Output for Sample Input 2

3

Explanation for Sample Output 2

The shortest route is 1 \to 2 of length 1, and the strictly-second route is 1 \to 2 \to 1 \to 2 of length 3.


Comments