UVA1347 - Tour (DAG上的DP)

题目链接  UVA1347

【题意】

《算法竞赛入门经典第二版》上的直接上图吧

【分析】

【AC代码】9ms

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define MAXN 1010
#define dis(a,b) sqrt((p[a].x - p[b].x)*(p[a].x - p[b].x) + (p[a].y - p[b].y)*(p[a].y - p[b].y))
struct NODE{
int x, y;
}p[MAXN];
double dp[MAXN][MAXN];
//dp[i][j]表示第一个人到达了i,第二个人在j时(i>j，并且i之前的点都已经走过)还最少需要多少距离到达终点
int main()
{
#ifdef SHY
freopen("e:\1.txt", "r", stdin);
#endif
int n;
while (~scanf("%d%*c", &n))
{
double buf;
for (int i = 1; i <= n; i++)
scanf("%d %d%*c", &p[i].x, &p[i].y);
buf = dis(n-1,n);
for (int i = 1; i <= n; i++)//初始化
dp[n - 1][i] = buf+dis(i,n);
for (int i = n - 2; i >= 2; i--)//反过来直接填表
{
for (int j = i-1; j >= 1; j--)
dp[i][j] = min(dp[i + 1][j] + dis(i, i + 1), dp[i + 1][i] + dis(j, i + 1));
}
printf("%.2lfn", dp[2][1]+dis(1,2));
}
return 0;
}

最后

以上就是妩媚柚子为你收集整理的UVA1347 - Tour (DAG上的DP)的全部内容，希望文章能够帮你解决UVA1347 - Tour (DAG上的DP)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。