No.3490 最高経路問題
p-adic問題文
最初に $2$ 個の正整数 $N, M$ が与えられます。
ある山には $N$ 個の村と、それらを双方向に結ぶ $M$ 本のトンネルがあります。
村は $N$ 以下の各正整数 $i$ で番号付けられ村 $i$ と呼ばれます。
トンネルは $M$ 以下の各正整数 $j$ で番号付けられトンネル $j$ と呼ばれ、トンネル $j$ は村 $u_j$ と村 $v_j$ を結んでおり（$u_j, v_j$ は $u_j < v_j$ を満たす $N$ 以下の正整数）、車高制限が $h_j$ です（$h_j$ は正整数）。
直進大好きbotはこの山のトンネルを直進するのが大好きなbotです。
直進大好きbotはなるべく車高の高いトラックでトンネルのみを直進し村 $1$ から村 $N$ に向かおうとしています。
ただし任意の正整数 $h$ に対し、車高 $h$ のトラックで直進できるのは車高制限が $h$ 以上のトンネルに限られます。
車高 $1$ のトラックでトンネルのみを直進して村 $1$ から村 $N$ へ到達する経路が存在するか否かを判定してください。
存在する場合は更に、車高 $h$ のトラックでトンネルのみを直進して村 $1$ から村 $N$ へ到達する経路が存在するような正整数 $h$ の最大値を求めてください。
入力
入力は以下の形式で標準入力から $1 + M$ 行で与えられます：
- $1$ 行目に $N, M$ が半角空白区切りで与えられます。
- $M$ 以下の各正整数 $j$ に対し、$1 + j$ 行目に $u_j , v_j , h_j$ が半角空白区切りで与えられます。
$N$ $M$ $u_1$ $v_1$ $h_1$ $\vdots$ $u_M$ $v_M$ $h_M$
制約
入力は以下の制約を満たします：
- $N$ は $2 \leq N \leq 10^5$ を満たす整数である。
- $M$ は $1 \leq M \leq 10^5$ を満たす整数である。
- $M$ 以下の任意の正整数 $j$ に対し、
- $u_j, v_j$ は $1 \leq u_j < v_j \leq N$ を満たす整数である。
- $h_j$ は $1 \leq h_j \leq 10^9$ を満たす整数である。
出力
車高 $1$ のトラックでトンネルのみを直進して村 $1$ から村 $N$ へ到達する経路が存在しないならば、NaNと $1$ 行目に出力してください。
存在するならば、車高 $h$ のトラックでトンネルのみを直進して村 $1$ から村 $N$ へ到達する経路が存在するような正整数 $h$ の最大値を $1$ 行目に出力してください。
なお後者のケースにおいて最大値が存在することは、この問題の制約下で証明可能です。
最後に改行してください。
サンプル
サンプル1
入力
2 1 1 2 1
出力
1
車高制限 $1$ のトンネル $1$ が村 $1$ と村 $2$ を結んでいます。
$\displaystyle \begin{array}{ccc} \displaystyle 1 &\displaystyle \stackrel{h_1 = 1}{\longleftrightarrow} &\displaystyle 2 \end{array} $
車高 $1$ のトラックでトンネルを直進して村 $1$ から村 $N = 2$ へ到達するにはトンネル $1$ を通ればよいです。
一方で車高 $2$ のトラックではトンネルを直進して村 $1$ から村 $N = 2$ へ到達できません。
サンプル2
入力
3 2 1 2 1 1 2 2
このように複数のトンネルが同じ村の組を結びうることに注意してください。
出力
NaN
車高制限 $1$ のトンネル $1$ が村 $1$ と村 $2$ を結んでおり、車高制限 $2$ のトンネル $1$ が村 $1$ と村 $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} $
車高 $1$ のトラックでトンネルを直進して村 $1$ から村 $N = 3$ へ到達できません。
サンプル3
入力
4 4 1 2 3 1 3 2 2 4 1 3 4 2
出力
2
車高制限 $3$ のトンネル $1$ が村 $1$ と村 $2$ を結んでおり、車高制限 $2$ のトンネル $1$ が村 $1$ と村 $3$ を結んでおり、車高制限 $1$ のトンネル $3$ が村 $2$ と村 $4$ を結んでおり、車高制限 $2$ のトンネル $4$ が村 $3$ と村 $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} $
車高 $1$ のトラックでトンネルを直進して村 $1$ から村 $N = 4$ へ到達するには、例えばトンネル $1$ とトンネル $3$ をこの順に通るか、トンネル $2$ とトンネル $4$ をこの順に通ればよいです。
車高 $2$ のトラックでも後者の経路を通れます。一方で車高 $3$ のトラックではトンネルを直進して村 $1$ から村 $N = 4$ へ到達できません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。