#Psmt18. 4.保留道路
4.保留道路
4.保留道路
题目描述
有个国家有N个城市,城市由1,2,3,...,N标号,城市间有M条双向道路,每条道路都有两个属性g和s,两个城市间可能有多条道路,并且可能存在将某一城市与其自身连接起来的道路。后来由于战争的原因,国王不得不下令减小花费从而关闭一些道路,但是必须要保证任意两个城市相互可达。
道路花费的计算公式为wGmax{所有剩下道路的属性g}+wSmax{所有剩下道路的属性s},其中wG和wS是给定的值。国王想要在满足连通性的前提下使这个花费最小,现在需要你计算出这个花费。
输入格式
第一行包含两个正整数N和M。
第二行包含两个正整数wG和wS。
后面的M行每行描述一条道路,包含四个正整数u,v,g,s,分别表示道路连接的两个城市以及道路的两个属性。
输出格式
输出一个整数,表示最小花费。
若无论如何不能满足连通性,输出-1。
数据范围
(原站未提供,导入后需人工补齐)
样例
3 3
2 1
1 2 10 15
1 2 4 20
1 3 5 1
30
提示
对于10%的数据,N<=10,M<=20;
对于30%的数据,N<=100,M<=1000;
对于50%的数据,N<=200,M<=5000;
对于100%的数据,N<=400,M<=50000,wG,wS,g,s<=10 0000 0000。