本文共 769 字，大约阅读时间需要 2 分钟。
原题链接：
分类：DAG 备注：经典问题#includeusing namespace std;const int maxn=1e3+5;struct Point{ int x,y;}p[maxn];int n;double dis[maxn][maxn],res[maxn][maxn];double dp(int i,int j){ if(res[i][j]!=0.0)return res[i][j]; if(i==n-1)return res[i][j]=dis[n-1][n]+dis[j][n]; return res[i][j]=min(dp(i+1,j)+dis[i][i+1],dp(i+1,i)+dis[j][i+1]);}int main(void){ // freopen("in.txt","r",stdin); while(~scanf("%d",&n)){ memset(res,0,sizeof(res)); for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) dis[i][j]=dis[j][i]=sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y)); printf("%.2f\n",dp(2,1)+dis[1][2]); } return 0;}
转载地址：http://otel.baihongyu.com/