No.1639 Minimum Communication Channels
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
harurun
magsta