设为首页 加入收藏

TOP

UVA1347---Tour(dp,双调TSP)
2015-11-21 01:01:12 来源: 作者: 【大 中 小】 浏览:1次
Tags：UVA1347---Tour 双调 TSP

dp[i][j] 表示在1~max(i,j)都已经被走过的情况下,第一个人在i点,第二个人在j点时,走完剩下的点还需要的最短距离
规定第一个人领先第二个人
所以 dp[i][j] 可以转移到 dp[i+1][j] 和 dp[i+1][i] (等价于 dp[i][i+1] )

/*************************************************************************
    > File Name: 平常练习/uva1347.cpp
    > Author: ALex
    > Mail: zchao1995@gmail.com 
    > Created Time: 2015年05月25日 星期一 20时27分03秒
 ************************************************************************/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include
              #include 
              
                #include 
               
                 #include 
                
                  using namespace std; const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const double eps = 1e-15; typedef long long LL; typedef pair 
                 
                   PLL; double dp[1100][1100]; PLL point[1100]; double dist(PLL a, PLL b) { int x = a.first - b.first; int y = a.second - b.second; return sqrt(x * x * 1.0 + y * y * 1.0); } int main() { int n; while (~scanf("%d", &n)) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { dp[i][j] = 1000000000.0; } } int x, y; dp[1][1] = 0.0; for (int i = 1; i <= n; ++i) { scanf("%d%d", &x, &y); point[i] = make_pair(x, y); } for (int i = 1; i < n - 1; ++i) { for (int j = 1; j <= i; ++j) { if (dp[i][j] != 1000000000.0) { double d = dist(point[i + 1], point[i]); dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + d); d = dist(point[i + 1], point[j]); dp[i + 1][i] = min(dp[i + 1][i], dp[i][j] + d); } } } double ans = 1000000000.0; for (int i = 1; i < n - 1; ++i) { ans = min(ans, dp[n - 1][i] + dist(point[n - 1], point[n]) + dist(point[n], point[i])); } printf("%.2f\n", ans); } return 0; }
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：[C++] auto类型说明符 下一篇：C++刷题――{A} + {B} 实现集合的..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: