vijosP1014 旅行商简化版

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

vijosP1014 旅行商简化版

链接：https://vijos.org/p/1014

【思路】

双线DP。

设ab，ab同时走。用d[i][j]表示ab所处结点i、j，且定义i>j，则有转移方程：

d[i][j]=min{ d[i+1][j]+dist(i,i+1),d[i+1][i]+dist(j,i+1) };

另外需要注意坐标也需要用double读入。

（vj貌似出了些许问题，无论是我的代码还是以前AC的人的代码都过不了）

【代码】

 #include<cstdio>

 #include<cmath>

 #include<cstdlib>

 #include<algorithm>

 using namespace std;

 const int maxn = +;

 struct Node{

     double x,y;

     bool operator<(const Node& rhs) const{

        return x<rhs.x || (x==rhs.x && y<rhs.y);

     }

 }nodes[maxn];

 double f[maxn][maxn];

 bool vis[maxn][maxn];

 int n;

 inline double dist(int i,int j){

     return sqrt((nodes[i].x-nodes[j].x)*(nodes[i].x-nodes[j].x)+(nodes[i].y-nodes[j].y)*(nodes[i].y-nodes[j].y));

 }

 double dp(int i,int j) {

     double &ans=f[i][j];

     if(vis[i][j]) return ans;

     vis[i][j]=;

     if(i==n) return ans=dist(j,n);

     return ans=min(dp(i+,j)+dist(i,i+),dp(i+,i)+dist(j,i+));

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;i++) scanf("%lf%lf",&nodes[i].x,&nodes[i].y);

     sort(nodes+,nodes+n+);

     if(n==) printf("0.00\n");

     else printf("%.2lf\n",dp(,)+dist(,));

     return ;

 }