RT，一直是 76pts，模拟退火/随机

随机：

#include<bits/stdc++.h>
using namespace std;
int n,k,w;
bool t[55];
int r[55],ex[55];
int a[55][55];
const double o=0.9999,e=1e-8;
int ask()
{
	int i,j,mx=0,mn;
	random_shuffle(ex,ex+w);
	for(i=0;i<k;i++)
		t[ex[i]]=1;
	
	for(i=0;i<n;i++)
	{
		mn=1e9;
		for(j=0;j<n;j++)
			if(t[j])
				mn=min(mn,a[i][j]);
		mx=max(mn,mx);
	}			
	
	for(i=0;i<k;i++)
		t[ex[i]]=0;
	return mx;
}
int main()
{
	srand(time(0));
	int m,i,j,d,mn=1e9;
	cin>>n>>m>>k;
	for(i=0;i<n;i++)
		cin>>r[i];
	memset(a,127/3,sizeof(a));
	
	for(i=0;i<n;i++)
	{
		cin>>d;
		a[i][r[i]]=a[r[i]][i]=min(d,a[r[i]][i]);
	}
	for(i=0;i<n;i++)
		a[i][i]=0;
	for(int k=0;k<n;k++)
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
//	for(i=0;i<n;i++,cout<<endl)
//			for(j=0;j<n;j++)
//				cout<<a[i][j]<<' ';
	while(m--)
	{
		cin>>d;
		t[d]=1;
	}
	for(i=0;i<n;i++)
		if(!t[i])
			ex[w++]=i;
	while(clock()<1000000*0.75)
		mn=min(mn,ask());
	cout<<mn;
}

模拟退火：

#include<bits/stdc++.h>
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
int n,k,w,w2,mn=1e9;
bool t[55];
int r[55],ex[55],ex2[55],ans[55];
int a[55][55];
const double o=0.99999,e=1e-8;
int ask()
{
	int i,j,mx=0,mn;
	for(i=0;i<n;i++)
	{
		mn=1e9;
		for(j=0;j<k;j++)
			mn=min(mn,a[i][ex[j]]);
		mx=max(min(mn,ans[i]),mx);
	}			
	return mx;
}
void SA()
{
	double s=1,ans;
	int w1,w2;
	for(;s>e;s*=o)
	{
		w1=rand()%k,w2=rand()%(w-k)+k;
		swap(ex[w1],ex[w2]);
		ans=ask();
		if(ans<mn)
			mn=ans;
		else if(exp((ans-mn)/s)*RAND_MAX<rand())
			swap(ex[w1],ex[w2]);
		if(clock()>1000000*0.75) return;
	}
}
int main()
{
	srand(time(0));
	int m,i,j,d;
	cin>>n>>m>>k;
	if(m+k==n)
	{
		cout<<ask();
		return 0;
	}
	for(i=0;i<n;i++)
		cin>>r[i];
	memset(a,127/3,sizeof(a));
	memset(ans,127/3,sizeof(ans));
	for(i=0;i<n;i++)
	{
		cin>>d;
		a[i][r[i]]=a[r[i]][i]=min(d,a[r[i]][i]);
	}
	for(i=0;i<n;i++)
		a[i][i]=0;
	for(int k=0;k<n;k++)
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
//	for(i=0;i<n;i++,cout<<endl)
//			for(j=0;j<n;j++)
//				cout<<a[i][j]<<' ';
	while(m--)
	{
		cin>>d;
		ex2[w2++]=d;
		t[d]=1;
	}
	for(i=0;i<n;i++)
		for(j=0;j<w2;j++)
			ans[i]=min(ans[i],a[i][ex2[j]]);	
	for(i=0;i<n;i++)
		if(!t[i])
			ex[w++]=i;
	while(clock()<1000000*0.75)
		SA();
	cout<<mn;
}