問題一覧 > 通常問題

No.1639 Minimum Communication Channels

レベル : / AI推定難易度 : 600 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 184
作問者 : harurun / テスター : 👑 箱星 magsta
お気に入りにしたユーザー ProblemId : 6677 / 自分の提出
問題文最終更新日: 2021-08-06 19:19:46
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 308 (順位表) の他の問題:

Problem Statement

There are $N$ radio towers, numbered $1\sim N$.

Each radio tower can transmit radio waves within a circle (including its circumference) whose radius is a certain positive integer $r$.

You may build any number of bidirectional communication channels between radio towers.

Building a communication channel between radio towers $a_i$ and $b_i$ costs an amount equal to the distance $C_i$ between $a_i$ and $b_i$. $(1≤i≤N(N-1)/2)$

Radio towers $x$ and $y$ can communicate with each other in both directions if either of the following conditions is satisfied.

  • A communication channel is built between $x$ and $y$, and the distance between $x$ and $y$ is at most $r$.

  • Choose $k\ (>0)$ radio towers $(t_1,t_2,...,t_k)$ not including $x,y$. Then, communication channels are built between all of $x$ and $t_1$, $t_1$ and $t_2$, ..., $t_k$ and $y$, and the distances between $x$ and $t_1$, $t_1$ and $t_2$, ..., $t_k$ and $y$ are all at most $r$.

Your goal is to make communication possible between any pair of radio towers.

Find the minimum value of the positive integer $r$ when the communication channels are built so that the total cost is minimized.

However, if there are multiple ways of building that minimize the total cost, find the minimum value of the positive integer $r$ for each way of building, and then find the smallest among those values.

Constraints

  • $2≤N≤10^2$

  • $a_i\neq b_i$

  • For any distinct $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}}}$

  • All inputs are integers

Input

$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}$
  • The $1$ st line gives the number of radio towers.

  • Lines $2$ through $N(N-1)/2+1$ each give $a_i,b_i,C_i$ separated by spaces, meaning that the distance between radio towers $a_i$ and $b_i$ is $C_i$.

Output

Print the answer on one line. End the output with a newline.

Sample

Sample 1
Input
2
1 2 1
Output
1

The distance between radio tower $1$ and radio tower $2$ is $1$, and no smaller positive integer satisfies the condition, so print $1$.

Sample 2
Input
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
Output
5

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