2012 Canadian Computing Competition, Stage 2

Day 1, Problem 2: The Hungary Games

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 Széchenyi thermal bath (s for short) and ending at the Tomb of Gül 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 Pálvölgyi 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 visists some nodes more than once; see Sample Input 2 for an example.

Input Format

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, ..., 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 ≠ B on these lines, and that the ordered pairs (A, B) are distinct.

Output Format

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 10000. For 50% of the test cases, we will have 2 ≤ N ≤ 40 and 0 ≤ M ≤ 1000. All test cases will have 2 ≤ N ≤ 20000 and 0 ≤ M ≤ 100000.

Sample Input 1

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

Sample Output 1

11

Explanation

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

Sample Input 2

2 2
1 2 1
2 1 1

Sample Output 2

3

Explanation

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

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: Jun 20, 2012

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)