問題一覧 > 通常問題

No.1639 最小通信路

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 142
作問者 : harurunharurun / テスター : 👑 koboshikoboshi magstamagsta
2 ProblemId : 6677 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-08-06 19:19:46

問題文

$N$ 個の電波塔があり、各電波塔はそれぞれ $1\sim N$ の番号が付いています。

各電波塔は、ある正整数 $r$ を半径とした円内(円周も含む)に電波を飛ばすことが出来ます。

あなたは各電波塔間に好きな数、双方向の通信路を建設することができます。

電波塔 $a_i$ と $b_i$ の間に通信路を建設する場合、$a_i$$b_i$ 間の距離 $C_i$ と等しいコストがかかります。$(1≤i≤N(N-1)/2)$

電波塔 $x$ と電波塔 $y$ は以下の条件のどちらかを満たすとき双方向に通信することができます。

  • $x$$y$ 間に通信路が建設されていて、 $x$$y$ 間の距離が $r$ 以下である。

  • $x,y$ を含まない $k\ (>0)$ 個の電波塔 $(t_1,t_2,...,t_k)$ を選ぶ。 このとき、$x$$t_1$ 間、$t_1$$t_2$ 間、...、$t_k$$y$ 間の全てに通信路が建設されていて、 $x$$t_1$ 間、$t_1$$t_2$ 間、...、$t_k$$y$ 間のそれぞれの距離が全て $r$ 以下である。

あなたの目標は、任意の電波塔間の通信を可能にすることです。

かかるコストの総和が最小になるように通信路を建設したときの、正整数 $r$ の最小値を求めてください。

ただし、コストの総和が最小になる建設の仕方が複数ある場合は、それぞれの建設の仕方の正整数 $r$ の最小値を求め、その中での最小値を求めてください。

制約

  • $2≤N≤10^2$

  • $a_i\neq b_i$

  • 任意の異なる $i,j$ について $\{a_i,b_i\}\neq \{a_j,b_j\}$

  • $1≤a_i,b_i≤N$

  • $\boldsymbol{\textcolor{red}{1≤C_1<C_2<...<C_{N(N-1)/2}≤10^{100}}}$

  • 入力は全て整数

入力

$N$
$a_1\quad b_1\quad C_1$
$a_2\quad b_2\quad C_2$
$\vdots$
$a_{N(N-1)/2}\quad b_{N(N-1)/2}\quad C_{N(N-1)/2}$
  • $1$ 行目には 電波塔の数が与えられる。

  • $2$ から $N(N-1)/2+1$ 行目には、$a_i,b_i,C_i$ が空白区切りで与えられ、電波塔 $a_i$ と電波塔 $b_i$ の距離が $C_i$ であることを表す。

出力

答えを1行に出力してください。最後に改行してください。

サンプル

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

電波塔 $1$ と電波塔 $2$ の距離は $1$ であり、条件を満たすこれ以上小さな正整数はないので、$1$ を出力します。

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

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