#1512. [SCOI2008] 城堡 Castle
[SCOI2008] 城堡 Castle
题目描述
在一个国家里,有 个城市(编号为 到 )。这些城市之间有 条双向道路相连(编号为 到 ),其中编号为 的道路连接了城市 和城市 (一条道路可以连接一个城市和它自身),长度为 。 个城市中有 个拥有自己城堡,可以抵御敌人侵略。如果没有城堡的城市遭受攻击,则离它最近的城堡将派兵前往救援。
你的任务是在不超过 个没有城堡的城市中建立城堡,使得所有城市中“离最近城堡的距离”的最大值尽量小。换句话说,若令 表示城市 的最近城堡离它的距离,则你的任务是让 尽量小。
输入数据保证存在方案使得对于每个城市,至少有一个城堡能够到达。
输入格式
输入第一行为三个正整数 。第二行包含 个整数 。第三行包含 个整数 。第四行包含 个各不相同的 到 之间的整数,分别为 个城堡所在的城市编号。
输出格式
输出仅一行,包含一个整数,即 的最小值。
5 0 1
1 2 3 4 0
1 1 1 1 1
2
3 1 1
1 2 0
1 2 3
2
1
2 1 1
0 1
1 1
1
0
10 3 3
0 2 0 0 2 2 8 3 8 7
10 9 1 8 1 3 7 2 8 1
3 4 6
3
2 0 1
1 0
5 10
5
提示
的数据满足: ,,。