提交时间:2024-07-02 13:24:12

运行 ID: 153366

#include<bits/stdc++.h> using namespace std; double x[1010],y[1010],dis[1010][1010],dp[1010][1010]; double Dis(double x1,double y1,double x2,double y2){ return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } int main(){ int n,b1,b2; scanf("%d%d%d",&n,&b1,&b2); b1++; b2++; for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]); for(int i=1;i<n;i++)for(int j=i+1;j<=n;j++)dis[i][j]=dis[j][i]=Dis(x[i],y[i],x[j],y[j]); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=0x3f3f3f3f; dp[1][1]=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(i==j&&i!=1)continue; int k=max(i,j)+1; if(k==n+1){ if(i!=n)dp[n][n]=min(dp[n][n],dp[i][j]+dis[i][n]); if(j!=n)dp[n][n]=min(dp[n][n],dp[i][j]+dis[j][n]); } else{ if(k!=b1)dp[i][k]=min(dp[i][k],dp[i][j]+dis[j][k]); if(k!=b2)dp[k][j]=min(dp[k][j],dp[i][j]+dis[i][k]); } } printf("%0.2lf",dp[n][n]); return 0; }