3. 保留道路(road.cpp/c/pas) 【 问题描述 】 很久很久以前有一个国家，这个国家有N个城市，城市由1,2,3,…,N标号，城市间有M条双向道路，每条道路都有两个属性g和s，两个城市间可能有多条道路，并且可能存在将某一城市与其自身连接起来的道路。后来由于战争的原因，国王不得不下令减小花费从而关闭一些道路，但是必须要保证任意两个城市相互可达。 道路花费的计算公式为wG*max{所有剩下道路的属性g}+wS*max{所有剩下道路的属性s}，其中wG和wS是给定的值。国王想要在满足连通性的前提下使这个花费最小，现在需要你计算出这个花费。【 输入格式 】 输入文件名为road.in。 第一行包含两个正整数N和M。 第二行包含两个正整数wG和wS。 后面的M行每行描述一条道路，包含四个正整数u,v,g,s，分别表示道路连接的两个城市以及道路的两个属性。【 输出格式 】 输出文件名为road.out。 输出一个整数，表示最小花费。若无论如何不能满足连通性，输出-1。【 输入输出样例 】road.in road.out3 32 11 2 10 151 2 4 201 3 5 130【 数据规模与约定 】 对于10%的数据，N≤10，M≤20； 对于30%的数据，N≤100，M≤1000； 对于50%的数据，N≤200，M≤5000； 对于100%的数据，N≤400，M≤50000，wG,wS,g,s≤1000000000。
未解决
转载于:https://www.cnblogs.com/xiaoqi7/p/5997894.html
相关资源：你必须知道的495个C语言问题