問題一覧 > 通常問題

No.1308 ジャンプビーコン

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 44
作問者 : 👑 やむなくやむなく / テスター : 👑 りあんりあん
12 ProblemId : 2354 / 出題時の順位表
問題文最終更新日: 2020-12-06 13:40:16

注意

この問題は実行時間制限が厳しいので、高速な言語を使用することを推奨しています。 (C++, C#, PyPy3 で AC できることが確認されています。)

問題文

$N$ 頂点からなる木があります。この木の頂点には $1$ から $N$ までの番号がついていて、辺には $1$ から $N-1$ までの番号がついています。

辺 $i (1 \le i \le N-1)$ は、頂点 $u_i$ と頂点 $v_i$ を結ぶ、長さが $l_i$ の辺です。

正整数 $C$ と、長さ $Q$ の頂点列 $(x_1, x_2, \ldots, x_Q)$ が与えられます。

イカはいま頂点 $x_1$ にいて、これから $Q-1$ 個の頂点 $x_2, \ldots, x_Q$ を順番に訪れようとしています。

イカは次の $3$ つの行動から $1$ つを選んで行うことを繰り返します。

  • 現在いる頂点に接続する辺を $1$ つ選び、その辺が結ぶもう $1$ つの頂点へ移動する。

    • この行動には選んだ辺の長さ $l_i$ だけ時間がかかる。

  • 現在いる頂点にジャンプビーコンを $1$ 個設置する。

    • すでに木に設置されているビーコンがある場合、それは消滅し、現在位置のビーコン $1$ 個だけが残る。

    • この行動には時間はかからない。

  • ジャンプビーコンが設置されている頂点に移動する。

    • ジャンプビーコンは消滅する。

    • この行動には $C$ だけ時間がかかる。

イカが $Q-1$ 個の頂点を順番に訪れるのにかかる時間の最小値を求めてください。

入力

$N$ $Q$ $C$
$u_1$ $v_1$ $l_1$
$u_2$ $v_2$ $l_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$ $l_{N-1}$
$x_1$ $x_2$ $\ldots$ $x_Q$
  • $2 \le N,Q \le 3{,}000$
  • $1 \le C \le 10^9$
  • $1 \le u_i, v_i \le N (1 \le i \le N-1)$
  • $1 \le l_i \le 10^9 (1 \le i \le N-1)$
  • 与えられるグラフは木である。
  • $1 \le x_i \le N (1 \le i \le Q)$
  • $x_i \ne x_{i+1} (1 \le i \le Q-1)$
  • 入力はすべて整数である。

出力

イカが $Q-1$ 個の頂点を順番に移動するのにかかる時間の最小値を出力せよ。 最後に改行せよ。

サンプル

サンプル1
入力
3 5 1
1 2 1000
2 3 10
1 3 2 3 1
出力
1031

はじめ、イカは頂点 $1$ にいます。次の行動を順番に行います。

  1. 頂点 $1$ にジャンプビーコンを設置する。
  2. 辺 $1$ を選んで頂点 $2$ に移動する。時間が $l_1 = 1000$ かかる。
  3. 辺 $2$ を選んで頂点 $3$ に移動する。時間が $l_2 = 10$ かかる。
  4. 辺 $2$ を選んで頂点 $2$ に移動する。時間が $l_2 = 10$ かかる。
  5. 辺 $2$ を選んで頂点 $3$ に移動する。時間が $l_2 = 10$ かかる。
  6. ジャンプビーコンが設置されている頂点 $1$ に移動する。時間が $C = 1$ かかる。

時間を $1031$ だけかけて、頂点 $3, 2, 3, 1$ を順番に訪れることができます。

これよりかかる時間が少なくなるような行動のとり方は存在しないので、求める答えは $1031$ となります。

サンプル2
入力
6 5 3
1 5 3
6 5 2
4 6 2
3 5 2
5 2 5
1 2 3 4 5
出力
22
サンプル3
入力
2 10 1
1 2 1000000000
2 1 2 1 2 1 2 1 2 1
出力
5000000004

答えは 32bit 整数に収まらない可能性があります。

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