P2538城堡

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>
#include<time.h>
#include<queue>
using namespace std;
const double eps = 1e-14;
int n, m, k;
int ans1;
int a[60000], s[60000];
struct node
{
	int nxxt, to, w;
}e[60002]; int head[60000], tot;
int cnt, o[60000], city[60000];
void add(int a, int b, int w)
{
	e[++tot].nxxt = head[a];
	head[a] = tot;
	e[tot].to = b;
	e[tot].w = w;
}
int dis[6000], vis[6000];
int dijk()
{
    queue<int>q;
	memset(dis, 127, sizeof dis);
	memset(vis, 0, sizeof vis);
	for (int i = 1; i <= m; i++)q.push(city[i]), dis[city[i]] = 0;
	for (int i = 1; i <= k; i++)q.push(o[i]), dis[o[i]] = 0;
	while (!q.empty())
	{
		int u = q.front(); vis[u] = 0, q.pop();
		for (int i = head[u]; i; i = e[i].nxxt)
		{
			int v = e[i].to;
			if (dis[v] > dis[u] + e[i].w)
			{
				dis[v] = dis[u] + e[i].w;
				if (!vis[v])q.push(v);
			}
		}
	}
	int maxn = -1;
	for (int i = 1; i <= n; i++)maxn = max(maxn, dis[i]);
	return maxn;
}
int ed_ans;
void SA()
{
	int ans2;
	for (int T = 2000; T > eps; T *= 0.9949)
	{
		int x = rand() % k + 1, y = rand() % max(cnt - k, 1) + k;
		swap(o[x], o[y]);
		ans2 = dijk();
		if (ans2 < ans1)ans1 = ans2;
		else if (exp((ans1 - ans2) / T) * RAND_MAX <= rand())swap(o[x], o[y]);
	}
}
int fg[620];
int main()
{
	srand(0);
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++)scanf("%d", &s[i]);
	for (int i = 1; i <= n; i++)add(i, a[i] + 1, s[i]), add(a[i] + 1, i, s[i]);
	for (int i = 1, y; i <= m; i++)scanf("%d", &y), city[i] = y + 1, fg[y + 1] = 1;
	ans1 = dijk();
	for (int i = 1; i <= n; i++)if (!fg[i])o[++cnt] = i;
	if (n == m + k) { printf("0"); return 0; }
	while ((double)clock() / CLOCKS_PER_SEC <= 0.795)SA();
	printf("%d", ans1);
}