CCO '12 P2 - The Hungary Games - Olympiads Online Judge

CCO '12 P2 - The Hungary Games

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

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$ $s$ for short) and ending at the Tomb of Gul Baba ( $t$ $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$ $s$ - $t$ $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$ $s$ - $t$ $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$ $N$ $M$ $M$ , where $N$ $N$ is the number of nodes in Budapest and $M$ $M$ is the number of edges. The nodes are $1, 2, \dots, N$ $1, 2, \dots, N$ ; node $1$ $1$ represents $s$ $s$ ; node $N$ $N$ represents $t$ $t$ . Then there are $M$ $M$ lines of the form $A$ $A$ $B$ $B$ $L$ $L$ , indicating a one-way street from $A$ $A$ to $B$ $B$ of length $L$ $L$ . You can assume that $A \ne B$ $A \neq B$ on these lines, and that the ordered pairs $(A, B)$ $(A, B)$ are distinct.

Output Specification

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

Limits

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

Sample Input 1

Copy

Output for Sample Input 1

Copy

Explanation for Sample Output 1

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

Sample Input 2

Copy

2 2
1 2 1
2 1 1

Output for Sample Input 2

Copy

Explanation for Sample Output 2

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

Comments

0

Viv_CCGS commented on Nov. 20, 2024, 5:04 a.m.

Is it guaranteed that there exists an s-t path?

-5

qiuxinrong27 commented on Jan. 18, 2019, 4:07 p.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

3

noYou commented on May 6, 2020, 11:33 p.m.

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