OI题库

【题目描述】

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