56分求助
查看原帖
56分求助
242490
lyc呐楼主2021/9/3 14:54
#include<bits/stdc++.h>
#include<sstream>
#include<cstring>
#include<cmath>
#include<map>
#include<iomanip>
#include<bitset> 
#include<unordered_set>
#include<unordered_map>
#define IOS     cin.tie(0), ios::sync_with_stdio(false) 
#define x first
#define y second

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const int N = 55, M = N * 2, mod = 1e9 + 7, INF = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int P = 131;

int n, m, k;
int r[N];
int d[N];
int dist[N];
bool st[N], vis[N], can[N];
int h[N], e[M], ne[M], w[M], idx;
int ans = 1e8;


void add(int a, int b, int c)
{
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx ++;
}

void dijkstra()
{
	memset(vis, 0, sizeof vis);
	memset(dist, 0x3f, sizeof dist);
	priority_queue<pii> q;
	for(int i = 0 ; i < n ; i ++)
		if(st[i] || can[i]) dist[i] = 0, q.push({0, i});
	
	while(q.size())
	{
		auto t = q.top();
		int u = t.y;
		q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		
		for(int i = h[u] ; ~i ; i = ne[i])
		{
			int j = e[i];
			if(dist[j] > dist[u] + w[i])
			{
				dist[j] = dist[u] + w[i];
				q.push({dist[j], j});
			}
		}
	}
}

int calc()
{
	dijkstra();
	int res = 0;
	for(int i = 0 ; i < n ; i ++) res = max(res, dist[i]);
	ans = min(ans, res);
	return res;
}

void simulate_anneal()
{
	for(double t = 1e4 ; t > 1e-4 ;)
	{
		int a = rand() % n, b = rand() % n;
		if(can[a] && st[b]) continue;
		if(can[b] && st[a]) continue;
		if(can[a] == can[b]) continue;
		
		{
			int pre = calc();
			swap(can[a], can[b]);
			int now = calc();
			int dt = now - pre;	//dt为负,一定接受,否则概率接受
			if(exp(-dt / t) < (double)rand() / RAND_MAX)
				 swap(can[a], can[b]);
		}
		t *= 0.9995;
	}
}

void solve()
{
	srand(time(0));
	cin >> n >> m >> k;
	if(m + k == n)
	{
		cout << 0;
		return;
	}
	memset(h, -1, sizeof h);
	for(int i = 0 ; i < n ; i ++) cin >> r[i];
	for(int i = 0 ; i < n ; i ++) cin >> d[i];
	for(int i = 0 ; i < n ; i ++)
	{
		add(i, r[i], d[i]);
		add(r[i], i, d[i]);
	}
	for(int i = 0 ; i < m ; i ++)
	{
		int x;
		cin >> x;
		st[x] = true;
	}
	for(int i = 0 ; i < n && k ; i ++)
		if(!st[i])	can[i] = true, k --;
	while((double)clock() / CLOCKS_PER_SEC < 0.6) 
//	for(int i = 0 ; i < 100 && (double)clock() / CLOCKS_PER_SEC < 0.6 ; i ++)
		simulate_anneal();
	
	cout << ans << "\n";
 } 
 

int main()
{
    IOS;
//    int T;
//    cin >> T;
//    for(int i = 1 ; i <= T ; i ++)
    {
        solve();    
     } 
     return 0;
}
2021/9/3 14:54
加载中...