求助!紧急!P1433 吃奶酪
查看原帖
求助!紧急!P1433 吃奶酪
919203
_Dynamic_Programming楼主2024/6/10 16:30

P1433 吃奶酪帮忙看一下,RE了,改了一天,请大佬们帮我查查错,非常感谢!

#include <bits/stdc++.h>
using namespace std;
int n;
double a[20], b[20], dp[(1 << 15) + 5][20], ans = 1e9;
bool used[20];
double dis(int x,int y)
{
    sqrt((a[x] - a[y]) * (a[x] - a[y]) + (b[x] - b[y]) * (b[x] - b[y]));
}
void dfs(int t, int now, double s, int bb)
{
    if(s > ans) return;
    if(t == n)
    {
	ans = min(ans, s);
	return ;
    }
    for(int i = 1; i <= n; i++)
    {
	if(used[i] == 0)
	{
	    int p = bb + (1 << (i - 1));
	    if(dp[p][i] != 0 && dp[p][i] <= s + dis(now, i)) continue;
	    used[i] = 1;
	    dp[p][i] = s + dis(now, i);
	    dfs(t + 1, i, dp[p][i], p);
	    used[i] = 0;
	}
    }
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%lf%lf", &a[i], &b[i]);
    dfs(0, 0, 0, 0);
    printf("%.2lf\n", ans);
    return 0;
}
2024/6/10 16:30
加载中...