No.2805 Go to School
タグ : / 解いたユーザー数 97
作問者 :
![highlighter](https://pbs.twimg.com/profile_images/1707374069132439552/b_BWx6c8.png)
![Magentor](https://pbs.twimg.com/profile_images/1715389554197495808/7HlNzj_p.jpg)
![keisuke6](https://pbs.twimg.com/profile_images/1675785204974354432/k3Bvkvyj.jpg)
![fact493](https://pbs.twimg.com/profile_images/1641449306531192836/GjfyenV1.jpg)
問題文
kuroinu君は家から学校に行こうとしています。
地点が $N$ 個あり、それぞれに $1,2\dots N$ と番号が振られています。
また、地点と地点を繋ぐ道が $M$ 本あり、道 $i(1\leq i\leq M)$ は地点 $a_i$ と地点 $b_i$ を双方向にそれぞれ $t_i$ 分かけて移動することができます。ここで、同じ地点どうしを結ぶ道がある可能性があること、同じ地点のペアに複数の道がある可能性があることに注意してください。
地点 $1$ にkuroinu君の家が、地点 $N$ に学校があります。
はじめ、kuroinu君は地点 $1$ にいます。
kuroinu君は、道を通って地点を移動すること、今いる地点に任意の時間とどまることができます。
$S$ 分後から $E+0.01$ 分間、kuroinuくんはお腹を痛くしてしまうため、その間にトイレに用を済ませに行く必要があります。
トイレは $L$ 個あり、地点 $T_j(1\leq j\leq L)$ にあります。ただし、$T_L=N$ です。また、トイレで用を済ますには $1$ 分かかります。
つまり、$S$ 分後から $S+E-0.99$ 分後の間にいずれかのトイレがある地点に到着し、そこに $1$ 分以上とどまる必要があります。
用を済ませたうえで学校にたどり着くのに最小で何分かかるかを求めてください。この問題の制約下で、この値は存在するなら整数であることが証明できます。
ただし、トイレに間に合わないもしくは学校までたどりつけない場合は-1
を出力してください。
入力
$N~~~M~~~L~~~S~~~E$ $a_1~~~b_1~~~t_1$ $a_2~~~b_2~~~t_2$ $\vdots$ $a_M~~~b_M~~~t_M$ $T_1~~~T_2~~~\dots~~~T_L$
制約
- $2\leq N\leq 2\times10^5$
- $1\leq M\leq 2\times10^5$
- $1\leq L\leq N$
- $1\leq S,E \leq 10^9$
- $1\leq a_i,b_i\leq N$
- $1\leq t_i\leq 10^9(1\leq i\leq M)$
- $1\leq T_1 \lt T_2 \lt \dots \lt T_L= N$
- 入力はすべて整数
出力
答えを $1$ 行に出力せよ。
また、最後に改行すること。
サンプル
サンプル1
入力
5 6 3 4 2 1 2 3 1 3 2 2 4 5 2 3 2 4 5 6 1 4 2 2 3 5
出力
15
地点 $1$ から地点 $3$ まで行き、$S$ 分になるまで待った後トイレで用を済ませ、地点 $5$ に行くのが最適です。
サンプル2
入力
4 4 4 5 3 1 2 2 1 3 3 1 4 4 2 3 1 1 2 3 4
出力
6
お腹が痛くなる前に学校に到着することが可能ですがトイレを済ませてからという条件があるので、学校である地点 $4$ のトイレを使用します。
サンプル3
入力
6 6 2 4 5 1 3 4 2 3 2 6 4 2 3 4 3 1 2 1 1 5 3 5 6
出力
9
地点 $6$ まで行き、地点 $6$ のトイレで用を済ませます。
サンプル4
入力
4 3 1 3 4 1 3 2 2 3 2 1 3 1 4
出力
-1
そもそも学校までたどり着くことができません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。