No.3490 Highest Path Problem
タグ : / 解いたユーザー数 46
作問者 : 👑
p-adic
Problem Statement
First, you are given $2$ positive integers $N, M$.
A certain mountain has $N$ villages and $M$ tunnels that connect them bidirectionally.
The villages are numbered by the positive integers $i$ not exceeding $N$, and each is called village $i$.
The tunnels are numbered by the positive integers $j$ not exceeding $M$, and each is called tunnel $j$. Tunnel $j$ connects village $u_j$ and village $v_j$ ($u_j, v_j$ are positive integers not exceeding $N$ that satisfy $u_j < v_j$), and its vehicle height limit is $h_j$ ($h_j$ is a positive integer).
Chokushin Daisuki Bot is a bot that loves going straight through the tunnels of this mountain.
Chokushin Daisuki Bot wants to travel from village $1$ to village $N$, going straight only through tunnels, in a truck with as large a vehicle height as possible.
However, for any positive integer $h$, a truck of vehicle height $h$ can go straight only through tunnels whose vehicle height limit is at least $h$.
Determine whether there exists a route from village $1$ to village $N$ that a truck of vehicle height $1$ can take by going straight only through tunnels.
If it exists, additionally find the maximum positive integer $h$ such that there exists a route from village $1$ to village $N$ that a truck of vehicle height $h$ can take by going straight only through tunnels.
Input
The input is given from standard input in $1 + M$ lines in the following format:
- Line $1$ contains $N, M$, separated by a single space.
- For each positive integer $j$ not exceeding $M$, line $1 + j$ contains $u_j , v_j , h_j$, separated by single spaces.
$N$ $M$ $u_1$ $v_1$ $h_1$ $\vdots$ $u_M$ $v_M$ $h_M$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $2 \leq N \leq 10^5$.
- $M$ is an integer satisfying $1 \leq M \leq 10^5$.
- For any positive integer $j$ not exceeding $M$:
- $u_j, v_j$ are integers satisfying $1 \leq u_j < v_j \leq N$.
- $h_j$ is an integer satisfying $1 \leq h_j \leq 10^9$.
Output
If there does not exist a route from village $1$ to village $N$ that a truck of vehicle height $1$ can take by going straight only through tunnels, print NaN on line $1$.
If it exists, print on line $1$ the maximum positive integer $h$ such that there exists a route from village $1$ to village $N$ that a truck of vehicle height $h$ can take by going straight only through tunnels.
Note that in the latter case, the existence of the maximum can be proved under the constraints of this problem.
Print a newline at the end.
Sample
Sample 1
Input
2 1 1 2 1
Output
1
Tunnel $1$ with vehicle height limit $1$ connects village $1$ and village $2$.
$\displaystyle \begin{array}{ccc} \displaystyle 1 &\displaystyle \stackrel{h_1 = 1}{\longleftrightarrow} &\displaystyle 2 \end{array} $
A truck of vehicle height $1$ can reach village $N = 2$ from village $1$ by going straight through tunnels by passing through tunnel $1$.
On the other hand, a truck of vehicle height $2$ cannot reach village $N = 2$ from village $1$ by going straight through tunnels.
Sample 2
Input
3 2 1 2 1 1 2 2
Note that, as in this case, multiple tunnels may connect the same pair of villages.
Output
NaN
Tunnel $1$ with vehicle height limit $1$ connects village $1$ and village $2$, and tunnel $1$ with vehicle height limit $2$ connects village $1$ and village $2$.
$\displaystyle \begin{array}{ccccc} \displaystyle 1 &\displaystyle \begin{array}{c} \stackrel{h_1 = 1}{\longleftrightarrow} \\ \stackrel{h_2= 2}{\longleftrightarrow} \end{array} &\displaystyle 2 &\displaystyle &\displaystyle 3 \end{array} $
A truck of vehicle height $1$ cannot reach village $N = 3$ from village $1$ by going straight through tunnels.
Sample 3
Input
4 4 1 2 3 1 3 2 2 4 1 3 4 2
Output
2
Tunnel $1$ with vehicle height limit $3$ connects village $1$ and village $2$, tunnel $1$ with vehicle height limit $2$ connects village $1$ and village $3$, tunnel $3$ with vehicle height limit $1$ connects village $2$ and village $4$, and tunnel $4$ with vehicle height limit $2$ connects village $3$ and village $4$.
$\displaystyle \begin{array}{rcl} \displaystyle 1 &\displaystyle \stackrel{h_1 = 3}{\longleftrightarrow} &\displaystyle 2 \\ \displaystyle {}_{h_2 = 2} \updownarrow &\displaystyle &\displaystyle \updownarrow_{h_3 = 1} \\ \displaystyle 3 &\displaystyle \stackrel{h_4 = 2}{\longleftrightarrow} &\displaystyle 4 \end{array} $
A truck of vehicle height $1$ can reach village $N = 4$ from village $1$ by going straight through tunnels by, for example, passing through tunnel $1$ and tunnel $3$ in this order, or through tunnel $2$ and tunnel $4$ in this order.
A truck of vehicle height $2$ can also take the latter route. On the other hand, a truck of vehicle height $3$ cannot reach village $N = 4$ from village $1$ by going straight through tunnels.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。