CCO '12 P2 - The Hungary Games

View as PDF

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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 ( for short) and ending at the Tomb of Gul Baba ( 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 - 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 - 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 , where is the number of nodes in Budapest and is the number of edges. The nodes are ; node represents ; node represents . Then there are lines of the form , indicating a one-way street from to of length . You can assume that on these lines, and that the ordered pairs are distinct.

Output Specification

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

Limits

Every length will be a positive integer between and . For 50% of the test cases, we will have and . All test cases will have and .

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 () and the strictly-second-shortest route is 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 of length 1, and the strictly-second route is of length 3.

• commented on Jan. 18, 2019, 11:07 a.m.

Literally the same as https://dmoj.ca/problem/ncco4d1p3

• commented on May 6, 2020, 7:33 p.m.

That problem uses an undirected graph, and has a far more strict time limit.

• commented on Feb. 6, 2018, 9:09 p.m. edited

Are the extra spaces at the end of the lines in the sample input intended?

• commented on Feb. 6, 2018, 10:14 p.m.

Fixed.