洛谷P1523 旅行商简化版(DP)

2019-10-17 08:59:34来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

洛谷P1523 旅行商简化版(DP)

题目:
P1523 旅行商简化版
解析
\(f[i][j]\)表示一个人走到i,一个人走到j的最短距离(\(i<j\)
\(j+1\)个位置,两个人都可能走,两种情况

  • \(f[i][j+1]=min\{f[i][j+1],f[i][j]+dis[j][j+1]\}\)位置在j的人走到了j+1位置
  • \(f[j][j+1]=min\{f[j][j+1],f[i][j]+dis[i][j+1]\}\)位置在i的人走到了j+1位置

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;

int n, m;
double f[N][N], dis[N][N];

struct node {
    double x, y;
    bool operator <(const node &oth) const {
        return x < oth.x;
    }
} e[N];

double calc(node a, node b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> e[i].x >> e[i].y;
    sort(e + 1, e + 1 + n);
    for (int i = 1; i <= n; ++i) 
        for (int j = i + 1; j <= n; ++j) 
            dis[i][j] = calc(e[i], e[j]), f[i][j] = LLONG_MAX;
    f[1][2] = dis[1][2];
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j) {
            f[i][j + 1] = min(f[i][j + 1], f[i][j] + dis[j][j + 1]);
            f[j][j + 1] = min(f[j][j + 1], f[i][j] + dis[i][j + 1]);
        }
    double ans = LLONG_MAX;
    for (int i = 1; i < n; ++i) ans = min(ans, f[i][n] + dis[i][n]);
    printf("%.2lf", ans);
}

原文链接:https://www.cnblogs.com/lykkk/p/11692713.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++之开灯问题(链表)

下一篇:QT使用LIBS添加绝对路径的dll引用