Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
150018 冼俊烨 巡逻线路 C++ 通过 100 0 MS 608 KB 1202 2024-06-01 14:24:48

Tests(5/5):


#include <bits/stdc++.h> using namespace std; #define N 1010 #define INF 0x3f3f3f3f double x[N],y[N],dis[N][N],dp[N][N]; double Dis(double x1,double y1,double x2,double y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } int main() { //freopen("path.in","r",stdin); //freopen("path.out","w",stdout); 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]=INF; 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\n",dp[n][n]); return 0; }


测评信息: