問題一覧 > 通常問題

No.614 壊れたキャンパス

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 65
作問者 : treeonetreeone / テスター : ふーらくたるふーらくたる
1 ProblemId : 2045 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-08-23 23:20:09
この問題はAdvent Calendar Contest Advent Calendar 2017の14日目の問題です.

問題文

$N$ 棟の建物が第 $1$ 棟から第 $N$ 棟まで順に並んでいる。
建物は全て $K$ 階建てであり、$1$ 階から $K$ 階まで階段を使って行き来できる。

さらに、これらの建物の間には $M$ 個の渡り廊下があり、
$i$ 番目の渡り廊下により第 $a_i$ 棟の $b_i$ 階から第 $a_i+1$ 棟の $c_i$ 階の方向にのみ移動できる。

T君は第 $1$ 棟の $S$ 階から 第 $N$ 棟の $T$ 階まで、できるだけ階段を使わないで移動したい。
この時、階段を上り下りする必要がある階数の最小値を求めよ。

ただし、T君は外に出たくないため、建物間の移動には渡り廊下のみを使う。
辿り着くことができない場合は $-1$ を出力せよ。

入力

$N$ $M$ $K$ $S$ $T$
$a_1$ $b_1$ $c_1$
$:$
$a_M$ $b_M$ $c_M$

1行目に $N$, $M$, $K$, $S$, $T$ が与えられる。
2行目からの $M$ 行に、渡り廊下の情報 $a_i$, $b_i$, $c_i$ が与えられる。
入力は全て整数で与えられ、以下の制約を満たす。
$1 \leqq N \leqq 2 \times 10^5$
$0 \leqq M \leqq 2 \times 10^5$
$1 \leqq K \leqq 10^9$
$1 \leqq S, T \leqq K$
$1 \leqq a_i \leqq N - 1$ ($1 \leqq i \leqq M$)
$1 \leqq b_i, c_i \leqq K$ ($1 \leqq i \leqq M$)
$(a_i, b_i, c_i) \neq (a_j, b_j, c_j) (i \neq j)$

出力

T君が階段を上り下りする必要がある最小の階数を出力し、最後に改行せよ。

サンプル

サンプル1
入力
2 1 5 1 5
1 3 4
出力
3

第1棟の1階から第1棟の3階まで2階分階段を使って移動し、渡り廊下で第2棟の4階に行く。
さらに階段を1階分上がることで、合計階段3階分で第2棟の5階に移動できる。

サンプル2
入力
2 2 10 10 1
1 9 5 
1 6 1
出力
4

サンプル3
入力
2 0 5 1 5
出力
-1

第1棟と第2棟をつなぐ渡り廊下がないので、第2棟の5階に辿り着くことはできません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。