4639: 搭积木
[Creator : ]
Description
萨摩耶拿了一堆木棒给 DDDDDD ,每条木棒有起点终点 u,vu,vu,v ,萨摩耶让 DDDDDD 求出这些边的最小生成树, DDDDDD 很快就完成了,萨摩耶不开心,就又让 DDDDDD 求出从 [L,R][L,R][L,R] 之间的边中选出边使图中联通块最少的情况下代价为多少。
给定一张图 nnn 个点 ,mmm 条边,每条边有 u,v,wu,v,wu,v,w 三个属性,u,vu,vu,v 表示边连接的两个点,www 表示这条边的代价,给定 [L,R][L,R][L,R] 这个区间,从中选择边连起来使图中联通块最少(不保证一定会形成整张图的生成树),在这种情况下的最小代价是多少。
给定一张图 nnn 个点 ,mmm 条边,每条边有 u,v,wu,v,wu,v,w 三个属性,u,vu,vu,v 表示边连接的两个点,www 表示这条边的代价,给定 [L,R][L,R][L,R] 这个区间,从中选择边连起来使图中联通块最少(不保证一定会形成整张图的生成树),在这种情况下的最小代价是多少。
Input
第一行三个整数 n,m,qn,m,qn,m,q。
接下来 mmm 行,每行 333 个整数,表示 ui,vi,wiu_i,v_i,w_iui,vi,wi。
再接下来 qqq 行 ,每行 222 个整数,表示 Li,RiL_i,R_iLi,Ri。
接下来 mmm 行,每行 333 个整数,表示 ui,vi,wiu_i,v_i,w_iui,vi,wi。
再接下来 qqq 行 ,每行 222 个整数,表示 Li,RiL_i,R_iLi,Ri。
Output
对于每次询问输出最小代价。
Sample 1 Input
3 5 2
1 3 2
2 3 1
2 1 6
3 1 7
2 3 7
2 5
3 4
Sample 1 Output
7
13