- Mã:
-
Div2.MINIGAME32.4:
GATHER
- Tên:
- Đàn bò di chuyển
- Dạng thi:
- oi
- Thang điểm:
- 10 điểm
- Giới hạn thời gian:
- 2 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- phuc
Bessie is planning the annual Great Cow Gathering for cows all across the country and, of course, she would like to choose the most convenient location for the gathering to take place.
Each cow lives in one of N (1 ≤ N ≤ 100,000) different barns (conveniently numbered 1..N) which are connected by N-1 roads in such a way that it is possible to get from any barn to any other barn via the roads. Road i connects barns Ai and Bi (1 ≤ Ai ≤ N; 1 ≤ Bi ≤ N) and has length Li (1 ≤ Li ≤ 1,000). The Great Cow Gathering can be held at any one of these N barns. Moreover, barn i has Ci (0 ≤ Ci ≤ 1,000) cows living in it.
When choosing the barn in which to hold the Cow Gathering, Bessie wishes to maximize the convenience (which is to say minimize the inconvenience) of the chosen location. The inconvenience of choosing barn X for the gathering is the sum of the distances all of the cows need to travel to reach barn X (i.e., if the distance from barn i to barn X is 20, then the travel distance is Ci*20). Help Bessie choose the most convenient location for the Great Cow Gathering.
Consider a country with five barns with [various capacities] connected by various roads of varying lengths. In this set of barns, neither barn 3 nor barn 4 houses any cows.
1 3 4 5 @--1--@--3--@--3--@[2] [1] | 2 | @[1] 2
Bessie can hold the Gathering in any of five barns; here is the table of inconveniences calculated for each possible location:
Gather ----- Inconvenience ------ Location B1 B2 B3 B4 B5 Total 1 0 3 0 0 14 17 2 3 0 0 0 16 19 3 1 2 0 0 12 15 4 4 5 0 0 6 15 5 7 8 0 0 0 15
If Bessie holds the gathering in barn 1, then the inconveniences from each barn are:
Barn 1 0 -- no travel time there! Barn 2 3 -- total travel distance is 2+1=3 x 1 cow = 3 Barn 3 0 -- no cows there! Barn 4 0 -- no cows there! Barn 5 14 -- total travel distance is 3+3+1=7 x 2 cows = 14
So the total inconvenience is 17.
The best possible convenience is 15, achievable at by holding the Gathering at barns 3, 4, or 5.
Input
* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains a single integer: Ci
* Lines N+2..2*N: Line i+N+1 contains three integers: Ai, Bi, and Li
Output
* Line 1: The minimum inconvenience possible
Sample Input
5 1 1 0 0 2 1 3 1 2 3 2 3 4 3 4 5 3
Sample Output
15
- Dòng 1: 1 số nguyên N (0 < N <= 10^5)- Dòng 2..N + 1: mỗi dòng chứa 1 số nguyên c[i] (0 <= c[i] <= 1000) là số con bò đang có trên đồng cỏ tương ứng- Dòng N + 2..2N: mỗi dòng chứa 3 số nguyên a[i],b[i],d[i] mô tả một con đường nối 2 đồng cỏ a[i] với b[i], có độ dài d[i] (0 < d[i] <= 1000)
- 1 số nguyên là tổng khoảng cách di chuyển nhỏ nhất trong tình huống tối ưu
Input Output 5 1 1 0 0 2 1 3 1 2 3 2 3 4 3 4 5 315
Giải thích ví dụ
Mô tả test ví dụ. Địa điểm tối ưu là đồng cỏ thứ 3:
- Con bò ở đồng cỏ 1 di chuyển quãng đường 1- Con bò ở đồng cỏ 2 di chuyển quãng đường 2- Con bò ở đồng cỏ 5 di chuyển quãng đường 6- Tổng khoảng cách: 1.1 + 2.1 + 6.2 = 15
Đồng cỏ 4 và 5 cũng cho kết quả tối ưu tương tự
Theme :
Mời bạn soạn code