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 for Sample Output 1
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 for Sample Output 2
The shortest route is of length 1, and the strictly-second route is
of length 3.
Comments
Is it guaranteed that there exists an s-t path?
This comment is hidden due to too much negative feedback. Show it anyway.
That problem uses an undirected graph, and has a far more strict time limit.