CCO '12 P2 - The Hungary Games

View as PDF

Submit solution

Points: 15
Time limit: 2.0s
Memory limit: 64M

Problem type
Canadian Computing Competition: 2012 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,\ldots, 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 \neq 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 \leq N \leq 40 and 0 \leq M \leq 1000. All test cases will have 2 \leq N \leq 20000 and 0 \leq M \leq 100000.

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

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

Sample Input 2

2 2
1 2 1
2 1 1

Output for Sample Input 2

3
Explanation

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


Comments