求助,只有10分
查看原帖
求助,只有10分
791994
liyanchenlycccccc楼主2023/8/25 13:18
#include <bits/stdc++.h>
using namespace std;
struct poi
{
  double x,y;
  bool visit;
  int num;
} pz[16];
int n;
double ans=1e9,dp[16][33000]= {0};
double dis(poi p1,poi p2)
{
  return sqrt((p1.x-p2.x)*(p1.x*p2.x)+(p1.y-p2.y)*(p1.y*p2.y));
}
void dfs(poi p,int e,int m,double s)
{
  if(e==n)
  {
    if(ans>s) ans=s;
    return;
  }
  for(int i=0; i<n; i++)
  {
    if(pz[i].visit) continue;
    int tmp=m+(1<<i);
    if(dp[i][tmp]==0||dp[i][tmp]>dp[p.num][m]+dis(pz[i],p))
    {
      dp[i][tmp]=dp[p.num][m]+dis(pz[i],p);
      pz[i].visit=1;
      dfs(pz[i],e+1,tmp,s+dis(pz[i],p));
      pz[i].visit=0;
    }
  }
}
int main()
{
  cin>>n;
  for(int i=0; i<n; i++)
  {
    cin>>pz[i].x>>pz[i].y;
    pz[i].visit=0;
    pz[i].num=i;
  }
  poi p= {0,0,1,0};
  dfs(p,0,0,0);
  printf("%.2lf",ans);
  return 0;
}
2023/8/25 13:18
加载中...