問題一覧 > 通常問題

No.1833 Subway Planning

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : rianoriano / テスター : milkcoffeemilkcoffee 👑 ygussanyygussany
2 ProblemId : 7447 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-01-10 19:13:29

問題文

yukicoder 市には $1$ から $N$ までの番号がついた $N$ 個の交差点があり、$N-1$ 本の双方向に通行できる道路でそれぞれ結ばれています。 ここで、任意の $2$ つの交差点間を、何本かの道路を通って行き来できることが保証されます(すなわち交差点を頂点、道路を辺とした木となります)。

このうち、$i$ 番目の道路は交差点 $A_i$ と $B_i$ を結んでおり、混雑度が $C_i$ となっています。また、市内の各道路の混雑度の最大値を「市全体の交通混雑度」と定め、 $D$ で表します。 あなたは $2$ つ交差点を選び、その $2$ 地点を結ぶ地下鉄を $1$ 本だけ建設することで、 $D$ の値をできるだけ小さくしたいと考えています。 地下鉄の建設によって各道路の混雑度が下記の影響を受ける時、 $D$ の達成可能な最小値はいくらでしょうか。

【混雑度の変化】
地下鉄が $2$ つの交差点 $p,q$ を結ぶとする。 このとき、$p,q$ 間の最短経路に含まれる道路について、そのような道路の混雑度の最小値を $m$ とすると、これらの道路の混雑度は全て同時に $m$ だけ減少する。 また、$p,q$ 間の最短経路に含まれない道路について、混雑度は変化しない。

入力

$N$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
...
$A_{N-1}$ $B_{N-1}$ $C_{N-1}$

  • $2\leq N\leq 2\times 10^5$
  • $1\leq A_i,B_i\leq N$ $(1\leq i\leq N-1)$
  • 与えられるグラフは木である
  • $1\leq C_i\leq 10^9$ $(1\leq i\leq N-1)$
  • 入力は全て整数である

出力

達成可能な「市全体の交通混雑度」$D$ の最小値を整数で出力してください。 最後に改行してください。

サンプル

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

与えられた情報は下の図の通りです。交差点 $2$ と $4$ を結ぶ地下鉄を建設すると図の【変化後】のようになり、市全体の交通混雑度 $D=1$ を達成できます。 これより小さくすることはできませんので、これが答えです。

サンプル2
入力
4
2 1 100
3 1 90
4 1 80
出力
80

地下鉄は $2$ つの交差点を選んで建設するものであり、特に分岐は許されていないことに注意してください。

サンプル3
入力
9
1 2 15
3 1 10
2 4 8
5 6 7
5 2 9
3 8 7
7 3 2
3 9 5
出力
8

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