程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA1347---Tour(dp,雙調TSP)

UVA1347---Tour(dp,雙調TSP)

編輯：C++入門知識

UVA1347---Tour(dp,雙調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: [email protected] 
    > 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;
}