P2538 [SCOI2008] Castle

2008 Sichuan NOI Qualifier.

In a country, there are $n$ cities (numbered $0$ to $n-1$). They are connected by $n$ bidirectional roads (numbered $0$ to $n-1$), where road $i$ connects city $i$ and city $r_i$ (a road may connect a city to itself) and has length $d_i$. Among the $n$ cities, $m$ of them have their own castles and can resist enemy invasions. If a city without a castle is attacked, the nearest castle will send troops to rescue it. Your task is to build castles in at most $k$ cities that currently do not have castles, so that the maximum among all cities of the distance to the nearest castle is as small as possible. In other words, let $dist(c)$ be the distance from city $c$ to its nearest castle; your task is to minimize $\max\{dist(c)\}$. The input guarantees that there exists a solution 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 have castles.

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

$100\%$ of the testdata satisfies: $2 \leq n \leq 50$, $1 \leq d_i \leq 10^6$, $0 \leq m \leq n - k$. Translated by ChatGPT 5