2 shunfurh shunfurh 于 2017.09.18 10:34 提问

Transport Goods

The HERO country is attacked by other country. The intruder is attacking the capital so other cities must send supports to the capital. There are some roads between the cities and the goods must be transported along the roads.

According the length of a road and the weight of the goods, there will be some cost during transporting. The cost rate of each road is the ratio of the cost to the weight of the goods transporting on the road. It is guaranteed that the cost rate is less than 1.

On the other hand, every city must wait till all the goods arrive, and then transport the arriving goods together with its own goods to the next city. One city can only transport the goods to one city.

Your task is find the maximum weight of goods which can arrive at the capital.

Input

There are several cases.

For each case, there are two integers N (2 <= N <= 100) and M in the first line, where N is the number of cities including the capital (the capital is marked by N, and the other cities are marked from 1 to N-1), and M is the number of roads.

Then N-1 lines follow. The i-th (1 <= i <= N - 1) line contains a positive integer (<= 5000) which represents the weight of goods which the i-th city will transport to the capital.

The following M lines represent M roads. There are three numbers A, B, and C in each line which represent that there is a road between city A and city B, and the cost rate of this road is C.

Process to the end of the file.

Output

For each case, output in one line the maximum weight which can be transported to the capital, accurate up to 2 demical places.

Sample Input

5 6
10
10
10
10
1 3 0
1 4 0
2 3 0
2 4 0
3 5 0
4 5 0

Sample Output

40.00

1个回答

caozhy
caozhy   Ds   Rxr 2017.10.02 23:46
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
N - Trucking HDU - 2962 Kurskal
A certain local trucking company would like to transport some goods on a cargo truck from one place to another. It is desirable to transport as much goods as possible each trip. Unfortunately, one can
ZOJ-1655 Transport Goods
Transport Goods Time Limit: 2 Seconds      Memory Limit: 65536 KB The HERO country is attacked by other country. The intruder is attacking the capital so other cities must send supports to th
zoj 1655 Transport Goods
题意:有很多城市的货物需要运送到首都去,但是中途会有运输费用,求可以运送到首都的货物的最大重量。 思路:对首都求一次单源最长路径,使到达首都的货物最多。需要注意两点⑴ 此图有重边。 ⑵有些货物无法送达。 代码: #include #include using namespace std; const int inf = 100000000; const int m
ZOJ 1655 Transport Goods
The HERO country is attacked by other country. The intruder is attacking the capital so other cities must send supports to the capital. There are some roads between the cities and the goods must be
ZOJ 1655 Transport Goods
最短路问题    Dijkstra 分析: 1)要使运输到第n个城市的重量最大,每个城市的货物重量与每一条路的费用率有关,每个边的权值就是费用率,所以我们只需求出每个城市到首都的最优路线就行。用Dij的话, 是单源最短路径,即求出从首都出发,到各城市的最优路线。所以起始点是n。 2)最优路线就是累计费用率c最大的路线,c的初始值是1 。所以每加上一条边,就乘以这条边的剩余费
zoj 1655 Transport Goods(Dijkstra~~)
<br />dijkstra~~~<br /> <br />自己想得挺麻烦的,而且一直错,看了某洋的,呃,明白了。。<br /> <br />我发现自己写代码都没有好好想想,感觉就是套公式,公式套不了就不会了。笨蛋啊。。。<br /> <br />这个需要自己想的,dis里面保存的是 每个城市货物到capital 的 最大 rate。这个想法很好啊。。。。<br /> <br />动动脑子吧。。<br /> <br />#include <stdio.h> #include <stdlib.h> #in
zoj 1655 Transport Goods(最短路径)
The HERO country is attacked by other country. The intruder is attacking the capital so other cities must send supports to the capital. There are some roads between the cities and the goods must be
zoj 1655 Transport Goods(dijkstra)
ZOJ Problem Set - 1655Transport GoodsTime Limit: 1 Second      Memory Limit: 32768 KB <br />The HERO country is attacked by other country. The intruder is attacking the
ZOJ1655 Transport Goods,Dijkstra算法
这一题很简单,也是用Dijkstra算法求N到每个顶点的最短路径。这里的最短路径,是指N到每个顶点的最大(1-ratio),而(1-ratio)就是顶点经过运输到达N的剩余货物比率。 /****************************************
zoj 1655 Transport Goods Dijkstra
Description The HERO country is attacked by other country. The intruder is attacking the capital so other cities must send supports to the capital. There are some roads between the cities and the goo