5282: KD-Graph
内存限制：128 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：9
解决：3
题目描述
Let’s call a weighted connected undirected graph of n vertices and m edges KD-Graph, if the
following conditions fulfill:
* n vertices are strictly divided into K groups, each group contains at least one vertice
* if vertices p and q ( p ≠ q ) are in the same group, there must be at least one path between p and q meet the max value in this path is less than or equal to D.
* if vertices p and q ( p ≠ q ) are in different groups, there can’t be any path between p and q meet the max value in this path is less than or equal to D.
You are given a weighted connected undirected graph G of n vertices and m edges and an integer K.
Your task is find the minimum non-negative D which can make there is a way to divide the n vertices into K groups makes G satisfy the definition of KD-Graph.Or −1 if there is no such D exist.
following conditions fulfill:
* n vertices are strictly divided into K groups, each group contains at least one vertice
* if vertices p and q ( p ≠ q ) are in the same group, there must be at least one path between p and q meet the max value in this path is less than or equal to D.
* if vertices p and q ( p ≠ q ) are in different groups, there can’t be any path between p and q meet the max value in this path is less than or equal to D.
You are given a weighted connected undirected graph G of n vertices and m edges and an integer K.
Your task is find the minimum non-negative D which can make there is a way to divide the n vertices into K groups makes G satisfy the definition of KD-Graph.Or −1 if there is no such D exist.
输入
The first line contains an integer T (1≤ T ≤5) representing the number of test cases.
For each test case , there are three integers n,m,k(2≤n≤100000,1≤m≤500000,1≤k≤n) in the first line.
Each of the next m lines contains three integers u,v and c (1≤v,u≤n,v≠u,1≤c≤109) meaning that there is an edge between vertices u and v with weight c.
For each test case , there are three integers n,m,k(2≤n≤100000,1≤m≤500000,1≤k≤n) in the first line.
Each of the next m lines contains three integers u,v and c (1≤v,u≤n,v≠u,1≤c≤109) meaning that there is an edge between vertices u and v with weight c.
输出
For each test case print a single integer in a new line.
样例输入 复制
2
3 2 2
1 2 3
2 3 5
3 2 2
1 2 3
2 3 3样例输出 复制
3
-1