首页 > 代码库 > Fire

Fire

【题目描述】

有N(1 < N <= 1000)个城市(编号为1~N),每对城市之间只有一条公路连接,政府需要在一些城市建立消防机构,每个城市建立消防机构所需的费用W(1 <= W <= 10000)不一定相同,如果一个城市没有消防机构,那么它与其最近的具有消防机构的城市距离不能超过D(0 <= D <= 10000),对于距离D,每个城市也不一定相同,现询问建立消防机构的合法方案最少费用是多少。

【输入描述】

第一行输入一个数T,表示数据组数;

对于每组数据,输入格式如下:

第一行输入一个正整数N;

第二行输入N个数,表示每个城市建立消防机构的费用W;

第三行输入N个数,表示每个城市与其最近的具有消防机构的城市最远距离D;

接下来N-1行,每行输入两个数U、V、L,表示城市U与城市V之间存在一条长度为L的公路。

【输出描述】

对于每组数据,输出一个数,表示答案。

【输入样例】

5

5

1 1 1 1 1

1 1 1 1 1

1 2 1

2 3 1

3 4 1

4 5 1

5

1 1 1 1 1

2 1 1 1 2

1 2 1

2 3 1

3 4 1

4 5 1

5

1 1 3 1 1

2 1 1 1 2

1 2 1

2 3 1

3 4 1

4 5 1

4

2 1 1 1

3 4 3 2

1 2 3

1 3 3

1 4 2

4

4 1 1 1

3 4 3 2

1 2 3

1 3 3

1 4 2

【输出样例】

2

1

2

2

3

Fire