#P2538. [SCOI2008] 城堡

    ID: 1546 远端评测题 800ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp搜索2008四川各省省选模拟退火

[SCOI2008] 城堡

题目背景

2008NOI四川省选

题目描述

在一个国家里,有 nn 个城市(编号为 00n1n-1)。这些城市之间有 nn 条双向道路相连(编号为 00n1n-1),其中编号为 ii 的道路连接了城市 ii 和城市 rir_i(一条道路可以连接一个城市和它自身),长度为 did_inn 个城市中有 mm 个拥有自己城堡,可以抵御敌人侵略。如果没有城堡的城市遭受攻击,则离它最近的城堡将派兵前往救援。

你的任务是在不超过 kk 个没有城堡的城市中建立城堡,使得所有城市中“离最近城堡的距离”的最大值尽量小。换句话说,若令 dist(c)dist(c) 表示城市 cc 的最近城堡离它的距离,则你的任务是让 max{dist(c)}\max\{dist(c)\} 尽量小。

输入数据保证存在方案使得对于每个城市,至少有一个城堡能够到达。

输入格式

输入第一行为三个正整数 n,m,kn, m, k。第二行包含 nn 个整数 r0,r1,,rn1r_0,r_1,\ldots,r_{n-1}。第三行包含 nn 个整数 d0,d1,,dn1d_0,d_1,\ldots,d_{n-1}。第四行包含 mm 个各不相同的 00n1n-1 之间的整数,分别为 mm 个城堡所在的城市编号。

输出格式

输出仅一行,包含一个整数,即 max{dist(c)}\max\{dist(c)\} 的最小值。

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

提示

100%100\% 的数据满足: 2n502\leq n\leq 501di1061\leq d_i\leq 10^60mnk0\leq m\leq n-k