dfs + 卡时100分,HACKWA求助
  • 板块P1433 吃奶酪
  • 楼主asd890123
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/29 19:49
  • 上次更新2024/4/29 19:50:35
查看原帖
dfs + 卡时100分,HACKWA求助
1074084
asd890123楼主2024/4/29 19:49
#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int n,cnt;
const int PIANFEN = 5e7;
double a[N], b[N], dis[1001][1001];//dis表示距离;
int vis[N];
double mina = 1e9;

void dfs(int j, int num, double ju)
{   
    cnt++;
    if (cnt > PIANFEN){
        
        printf("%.2lf\n",mina);
        exit(0);
        
    }
    if (ju > mina)
    {
       return;
    }
	if (num == n)
	{
		mina = min(ju, mina);
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if(!vis[i])
		{
			vis[i] = 1;
			dfs(i, num + 1, ju + dis[j][i]);
			vis[i] = 0;	
		}
	}
}

int main(){
    
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%lf%lf", &a[i], &b[i]);
	for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
	    dis[i][j] = sqrt((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));
	dfs(0, 0, 0);
	printf("%.2lf\n", mina);
	
	return 0;
}
2024/4/29 19:49
加载中...