#298. 【CTSC2017】网络
一个一般的网络系统可以被描述成一张无向连通图。图上的每个节点为一个服务器，连接服务器与服务器的数据线则看作图上的一条边，边权为该数据线的长度。两个服务器之间的通讯距离被定义为其对应节点之间最短路的长度。
现在，考虑一个当前图结构为树的网络系统。你作为该网络系统的管理员，被要求在这个系统中新加入一条给定长度的数据线。数据线可以连在任意两个服务器上。
你的任务是，求出在所有合法的方案中，通讯距离最远的两个服务器之间的最小距离。
输入格式
输入包含多组数据。对于每组数据，输入的第一行包含二个正整数 N,LN,L, 其中 NN表示服务器个数，LL 为新加入数据线的长度。
接下来 n−1n−1 行，第 ii 行有三个正整数 ai,bi,liai,bi,li，表示有一条长度为 lili 的数据线连接服务器 ai,biai,bi。服务器的编号为 1∼N1∼N。
输入的末尾以两个 00 作为结束。
输出格式
对于每组数据，输出一行一个整数，描述在所有合法的方案中，通讯距离最远的两个服务器之间的最小距离。
样例一
input
7 11 2 12 3 13 4 14 5 15 6 16 7 10 0
output
3
样例二
input
6 261 2 662 3 113 4 732 5 773 6 3310 471 2 862 3 693 4 414 5 265 6 412 7 733 8 774 9 25 10 650 0
output
143232
样例三
见样例数据下载。
限制与约定
一共有 20 个测试点。编号为 1∼201∼20。每个测试点为 5 分。
保证在任一测试点中，数据的组数不会超过 1515，且所有数据的 NN 之和不超过数据范围中标明的 NN 的最大值的 55 倍。
保证所有的输入数据均为不超过 231−1231−1 的非负整数，保证 N≥1N≥1。
保证数据合法。
对于给定的测试点，其限制条件如下表所示。
| 测试点 | NN | 测试点 | NN |
|---|---|---|---|
| 1 | ≤10≤10 | 11 | ≤20000≤20000 |
| 2 | ≤50≤50 | 12 | |
| 3 | ≤100≤100 | 13 | |
| 4 | 14 | ||
| 5 | ≤150≤150 | 15 | |
| 6 | ≤600≤600 | 16 | ≤100000≤100000 |
| 7 | 17 | ||
| 8 | 18 | ||
| 9 | ≤2000≤2000 | 19 | |
| 10 | 20 |
时间限制：1s1s
空间限制：512MB
#include#include #include #define maxn 210using namespace std;int n;long long map[maxn][maxn],a[maxn][maxn],ans=1000000000000000;void init(){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) map[i][j]=a[i][j];}void floyed(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(i==j||j==k||i==k)continue; map[i][j]=min(map[i][j],map[i][k]+map[k][j]); }}long long count(){ long long res=0; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++) res=max(res,map[i][j]); } return res;}int main(){ int l; while(1){ scanf("%d%d",&n,&l); ans=1000000000000000; if(n==0&&l==0)return 0; int x,y,z; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j)a[i][j]=10000000000000; for(int i=1;i