P269， 关键在于自己强制规定了 i是大于j的，
d(i,j)表示的是已经走过max(i,j)还需要的距离值，当然设d为还需要的距离值，这很常见。//然而自己不知道。。。
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<string> #include<cstring> #include<iomanip> #include<iostream> #include<stack> #include<cmath> #include<map> #include<vector> #define ll long long #define inf 0x3f3f3f3f #define INF 1000000000 #define bug1 cout<<"bug1"<<endl; #define bug2 cout<<"bug2"<<endl; #define bug3 cout<<"bug3"<<endl; using namespace std; const int maxn=1005; int x[maxn],y[maxn]; double dist[maxn][maxn]; double dp[maxn][maxn]; int main(){ int n; while(~scanf("%d",&n)){ memset(dp,inf,sizeof(dp)); for(int i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]); for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ dist[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j])); } } for(int i=n-1;i>=2;i--){ for(int j=1;j<i;++j){ if(i==n-1)dp[i][j]=dist[i][n]+dist[j][n]; else dp[i][j]=min(dist[i][i+1]+dp[i+1][j],dist[j][i+1]+dp[i+1][i]); } } printf("%.2lf\n",dist[2][1]+dp[2][1]);//这个2并不是真的就表示标号为2的点，而是最左边的第一个点和第二个点。。 } }
