3899:JLUCPC

题目描述
Dr. Skywind and Dr. Walkoncloud are planning to hold the annual JLU Collegiate Programming Contest. The contest was always held in the college of software in the past. However, they changed their minds and decided to find the most convenient location from all colleges this year.
Each college in JLU is located in one of the N (1 <= N <= 100,000) different locations (labeled as 1 to N) connected by N-1 roads. Any two colleges are reachable to each other. The Contest can be held at any one of these N colleges. Moreover, Road i connects college A_i and B_i (1 <= A_i <=N; 1 <= B_i <= N) and has length L_i (1 <= L_i <= 1,000). College i has T_i (0 <= T_i <= 1,000) teams participating in the contest.
When choosing the college to hold the Contest, Dr. Skywind wishes to minimize the inconvenience of the chosen location. The inconvenience of choosing college P is the sum of the distance that all teams need to reach college P (i.e., if the distance from college i to college P is 20, then the travel distance is T_i*20). Please help Dr. Skywind and Dr. Walkoncloud to choose the most convenient location for the contest.
输入解释
There are multiple test cases. For each case, the first line contains a single integer N, indicating the number of colleges. The next N lines describes T_1 to T_n. Then, each of the last N-1 lines will contain 3 integers, namely A_i, B_i and L_i.
输出解释
For each case, output the minimum inconvenience possible
输入样例
3
1
1
2
1 2 2
2 3 1
4
100
1
1
1
1 2 1
2 3 1
2 4 1
输出样例
4
5
来自杭电HDUOJ的附加信息
Recommend

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-3899

最后修改于 2020-10-25 23:08:05 UTC 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
15000/5000MS(Java/Others) 65536/65536K(Java/Others)

·

·

·

·

登陆或注册以提交代码