No.848 なかよし旅行

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 77
作問者 : chocoruskchocorusk / テスター : tempura_pptempura_pp
3 ProblemId : 2711 / 出題時の順位表

問題文

雪男君と雪女さんはyuki国に旅行に来ました。yuki国は $1, 2, \ldots , N$ の番号がついた $N$ 個の街と、$1, 2, \ldots, M$ の番号がついた $M$ 本の道からなります。道 $i$ ($1\leq i\leq M$) は街 $a_i$ と街 $b_i$ を双方向に結んでいます。$2$ 人の歩く速さは同じであり、道 $i$ を歩くのにかかる時間は $2$ 人とも $c_i$ 分です。ただし、道を途中で引き返すことはできません

$2$ 人ははじめ空港のある街 $1$ にいて、街 $P$ と街 $Q$ にある観光名所に歩いて行こうと思っていましたが、$T$ 分後には街 $1$ に戻っていなくてはならないことに気づきました。そこで $2$ 人は次を満たすように行動することにしました。

  • $2$ 人のうち少なくとも一方が街 $P$ を訪れる。
  • $2$ 人のうち少なくとも一方が街 $Q$ を訪れる。

しかし $2$ 人はとても仲良しなので、できるだけ $2$ 人で一緒に行動する時間を長くしたいです。$T$ 分間のうち $2$ 人一緒に行動できる時間の最大値を求めてください。

ただし、$2$ 人で同じ場所で待機している時間も一緒に行動する時間に含まれます。

入力

$N\ M\ P\ Q\ T$
$a_1\ b_1\ c_1$
$\ldots$
$a_M\ b_M\ c_M$

  • $3\leq N\leq 2000$
  • $2\leq M\leq 10^5$
  • $2\leq P < Q\leq N$
  • $1\leq T\leq 10^9$
  • $1\leq a_i < b_i\leq N$
  • $1\leq c_i\leq 10^9$
  • $i\neq j$ のとき $(a_i, b_i)\neq (a_j, b_j)$
  • 街 $1$ からすべての街に歩いて行くことができる。
  • 入力はすべて整数である。

出力

問題文の条件を満たしつつ $2$ 人一緒に行動できる時間の最大値を分単位で出力せよ。ただしどのように行動しても条件を満たすことができない場合は $-1$ を出力せよ。

サンプル

サンプル1
入力
4 3 2 4 15
1 3 2
3 4 4
2 3 3
出力
7

例えば次のように行動すればよいです。

  • 雪男君は街 $1\to 3\to 2\to 3$ と移動し、街 $3$ で $2$ 分待ってから街 $1$ に戻り、$3$ 分待つ。
  • 雪女さんは街 $1\to 3\to 4\to 3\to 1$ と移動し、街 $1$ で $3$ 分待つ。

このとき $2$ 人一緒に行動する時間は、$0$ 分後から $2$ 分後までと、$10$ 分後から $15$ 分後までの合計 $7$ 分です。$T$ 分より早く街 $1$ に戻ってもよく、その場合 $2$ 人で $T$ 分後まで街 $1$ にいる時間も一緒に行動する時間に含まれます。

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

$2$ 人で街 $1\to 3\to 2\to 3\to 4\to 3\to 1$ と移動し、街 $1$ で $2$ 分待てばよいです。

サンプル3
入力
4 3 2 4 10
1 3 2
3 4 4
2 3 3
出力
-1

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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。