[SCOI2008]城堡

题目背景 2008NOI四川省选

题目描述 在一个国家里，有n个城市（编号为0 到n-1）。这些城市之间有n条双向道

路相连（编号为0 到n-1），其中编号为i的道路连接了城市i和城市ri（一条道

路可以连接一个城市和它自身），长度为di。n 个城市中有m个拥有自己城堡，

可以抵御敌人侵略。如果没有城堡的城市遭受攻击，则离它最近的城堡将派兵前

往救援。

你的任务是在不超过k个没有城堡的城市中建立城堡，使得所有城市中“离

最近城堡的距离”的最大值尽量小。换句话说，若令dist©表示城市c的最近城

堡离它的距离，则你的任务是让max{dist©}尽量小。

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

输入格式 输入第一行为三个正整数n, m, k。第二行包含n个整数r0,r1,…,rn-1。第三行

包含n 个整数d0,d1,…,dn-1。第四行包含m 个各不相同的0~n-1 之间的整数，分

别为m个城堡所在的城市编号。

输出格式 输出仅一行，包含一个整数，即max{dist©}的最小值。

输入输出样例 输入 #1复制 5 0 1 1 2 3 4 0 1 1 1 1 1 输出 #1复制 2 输入 #2复制 3 1 1 1 2 0 1 2 3 2 输出 #2复制 1 输入 #3复制 2 1 1 0 1 1 1 1 输出 #3复制 0 输入 #4复制 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 输出 #4复制 3 输入 #5复制 2 0 1 1 0 5 10 输出 #5复制 5 说明/提示 100%的数据满足：2 for (j=1;jint i,j; memset(vis,0,sizeof(vis)); for (i=1;iint i,j; long long d; cin>>n>>m>>k; memset(dis,127/2,sizeof(dis)); for (i=1;i scanf("%lld",&d); dis[i][son[i]]=min(dis[i][son[i]],d); dis[son[i]][i]=min(dis[i][son[i]],d); r+=d; } for (l=1;l dis[i][j]=min(dis[i][j],dis[i][l]+dis[l][j]); } } for (i=1;i