P2454 [SCOI2008] Castle - Enhanced Data Version

Weakened version of the original problem: https://www.luogu.com.cn/problem/P2538

In a country, there are $n$ cities (numbered $0$ to $n-1$). These cities are connected by $n$ bidirectional roads (numbered $0$ to $n-1$). Road $i$ connects city $i$ and city $r_i$ (a road may connect a city to itself), with length $d_i$. Among the $n$ cities, $m$ of them have their own castles, which can resist enemy invasions. When a city without a castle is attacked, the nearest castle will send troops to rescue. Your task is to build castles in at most $k$ cities that currently do not have castles, so that the maximum “distance to the nearest castle” among all cities is as small as possible. In other words, let $dist(c)$ be the distance from city $c$ to its nearest castle; your goal is to minimize $\max\{dist(c)\}$. It is guaranteed that there exists a plan such that for every city, at least one castle can reach it.

The first line contains three positive integers $n, m, k$. The second line contains $n$ integers $r_0,r_1,\ldots,r_{n-1}$. The third line contains $n$ integers $d_0,d_1,\ldots,d_{n-1}$. The fourth line contains $m$ distinct integers between $0$ and $n-1$, which are the indices of the cities that already have castles.

Output a single line containing one integer: the minimum possible value of $\max\{dist(c)\}$.

Constraints: $100\%$ of the testdata satisfies $1\leq d_i\leq 10^5$ and $0\leq m\leq n-k$. - Subtask 1: $2 \leq n \leq 3000$. - Subtask 2: $2 \leq n \leq 10^5$. Translated by ChatGPT 5