Given an undirected graph with N vertices and M edges, you need to delete C edges, and keep the graph connected. Then we can calculate N⋅(N−1)2 shortest distances of pairs of vertices.
You goal is to maximize the K th maximum distance.
First line contains four integers, N,M,C,K.
Each of the next M lines contains two integers u,v,w, represents an edge between u and v which weighted w. It's guaranteed there is no multiple edges or self loops.
C lines, each line contains two integers, represents one deleted edge.
If your output is illegal, score is 0, otherwise it will be the Kth maxinum distance√sum of weight of edges in the original graph.
N=512
M of i th(1≤i≤50) input file is i⋅2606+516
C is random selected in range [1000,M−N]
K is random selected in range [1,N⋅(N−1)2]
The graph generation is, first generate a random tree, then add M−N+1 random edges on it.
w is random selected in range [1,109].
Test data will be regenerated with different seeds after the contest.
Score=3√6≈1.2247448713915892
Edge (1,2) can also reach this answer.