[POJ2152]消防站

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file poj_2152.in Output file poj_2152.out

【题目描述】

Z国有N座城市,编号为1到N。城市间有高速公路连接,并且每两个城市之间都有且仅有一条路径。最近Z国经常发生火灾,因此政府决定在一些城市修建一些消防站。在第K座城市修建消防站花费W(K)。不同城市的W值可能不同。如果城市K没有消防站,它和最近的有消防站的城市的距离不能超过D(K)。D对不同的城市也可能是不同的。为了节约预算,±希望你计算修建消防站的最小花费。

【输入格式】

输入数据的第一行有一个整数N,代表城市数量。(0<=N<=1000)

第二行有N个整数,第I个整数是W(I)(0<=W(i)<=10000)。

第三行有N个空格隔开的整数。第I个整数是D(I)(0<=D(I)<=10000)。

接下来的N-1行每行有三个整数u,v,w(1<=u,v<=N,0<L<=1000),代表城市u和城市v之间有一条长度为L的高速公路。

【输出格式】

输出一行一个整数,即修建消防站的最小花费。

【样例输入】

样例输入1:


5

1 1 1 1 1

1 1 1 1 1

1 2 1

2 3 1

3 4 1

4 5 1

样例输入2:


5

1 1 1 1 1

2 1 1 1 2

1 2 1

2 3 1

3 4 1

4 5 1

样例输入3:


5

1 1 3 1 1

2 1 1 1 2

1 2 1

2 3 1

3 4 1

4 5 1

样例输入4:


4

2 1 1 1

3 4 3 2

1 2 3

1 3 3

1 4 2

样例输入5:


4

4 1 1 1

3 4 3 2

1 2 3

1 3 3

1 4 2


【样例输出】

样例输出1:

2

样例输出2:

1

样例输出3:

2

样例输出4:

2

样例输出5:

3

【提示】

本题的输入输出格式和POJ上略有不同。

【来源】

POJ 2152 Fire

POJ Monthly,Lou Tiancheng