Back to Category
d212: [12.03] D - Armored Car
Keyword:

Difficulity: N/A | Test Data Sets: 1 (Hidden) | Judging: Traditional Judge
Accepted : 0 Times | Submit :8 Times | Clicks : 1085
Accepted : 0 Users | Submit : 2 Users | Accepted rate : 0%
Time Limit :2000 ms | Memory Limit : 64000 KBytes
Update : 2012-05-10 17:56

Content: English | Chinese(TW)

Every day, banks in a country of N cities connected by M bidirectional roads need to transport their cashes into the central bank, which is located in the city numbered 1. There is exactly one bank in every city, which is equipped with an armored car to transport money in safe.

Each armored car can only transport its carried cash to one of the city adjacent to its located city. In order to transport all of the cashes separated in individual cities to the central bank, one bank must wait for all cashes coming from some of its adjacent cities and transport these cashes plus its share to another adjacent city. After some iterations, all the cashes should be gathered to the central bank.

One day, the government decides to tax the cash transportation. Every road is assigned to a constant tax value. The tax paid when passing a road equals to the road’s tax value multiplies the amount transported through. The tax is immediately taken when every armored car is about to go, so the amount decreases when the armored car arrived.

Now if the amount of cash in every city is known, could you estimate at least how much the government should receive when all cashes are gathered to the central bank?

Technical Specification

  • 1 N 50000
  • 0 ≤ M ≤ 100000
  • 0 ≤ tax value of each road < 1
  • 0 initial amount of cash of each city 100000
  • All cities are able to reach each other by passing some roads.
  • There is at most one road connecting two given cities. 

Input:

There are several (no more than 10) test cases in the input file. Each test case begins with the integers N and M. Cities are numbered as 1,2,...N. In the next M lines there are three integers i, j, and k, indicating there is a road connecting city i and city j, with the tax value of this road equals to k. There are then N integers, of which the ith integer indicates the initial amount of cash of city i.

There will be two zeros at the end of input file to indicate the end of test cases. 

Output:

For each test case output least amount the government could receive when all cashes are gathered to the central bank. Output every result to two digits after decimal point in its own line. 

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
4 4 1 3 2
7 5 6 3 1 7 4 2
9 3 2 1 6 5 4 9 8 7

Sample Output :

4
13
9

Hint :

Author :


  Solve it!   Status Forum

C
C++
JAVA
PASCAL

Program running time may be affected by various factors. Check server system environment information here