Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
153366 | 陈家宝 | 巡逻线路 | C++ | 通过 | 100 | 0 MS | 612 KB | 999 | 2024-07-02 13:24:12 |
#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; }