POJ 2677 Tour

深碍√TFBOYSˉ_ 2021-12-18 14:29 162阅读 0赞

两个人同时从最左端出发，不会走相同的点，且出了起点和终点每个点恰好被一个人走一次，求到最右端的最小。

用dp\[i\]\[j\] 表示快的人走到i 慢的人走到\[j\]

走到i点的情况:

1. 快的小人走到i，则有dp\[i\]\[j\]=min(dp\[i\]\[j\],dp\[i-1\]\[j\]+dis(i-1,i));

2. 慢的小人走到i，则有dp\[i\]\[i-1\]=min(dp\[i\]\[i-1\],dp\[i-1\]\[j\]+dis(i,j));

最后，必然是快的小人走到终点n，我们还要搜寻慢的小人在那个位置时总的路径最短。

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #define MAX 110
    using namespace std;
    double dp[MAX][MAX];
    int x[MAX],y[MAX];
    
    double dis(int i,int j)
    {
        return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    }
    
    int main()
    {
        int n;
        while(scanf("%d",&n) != EOF)
        {
    
            for(int i = 1; i <= n; i++)
            {
                scanf("%d%d",&x[i],&y[i]);
            }
    
            for(int i = 1;i <= n;i++)
                for(int j = 1;j <= n;j++)
            {
                dp[i][j] = 1e10;
            }
            dp[1][1] = 0;
            for(int i = 2; i <= n; i++)
                for(int j = 1; j < i; j++)
                {
                    dp[i][j] = min(dp[i][j],dp[i-1][j] + dis(i-1,i));
                    dp[i][i-1] = min(dp[i][i-1],dp[i-1][j] + dis(i,j));
                }
    
            double temp = 1e10;
            for(int i = 1;i < n;i++)
                temp = min(temp , dp[n][i] + dis(i,n));
            printf("%.2f\n",temp);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Przz/p/5409838.html

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 3488-Tour KM

为什么可以这样拆点在 [这道题][Link 1] 都已经证明过代码： 1 //题目上面说了“The only exception is that the firs

妖狐艹你老母/ 2023年10月11日 09:33/ 0 赞/ 15 阅读

相关 Poj 1637 Sightseeing tour (混合图的欧拉回路判定)

题意：给出一个混合图，要求判定欧拉回路是否存在，输入 x y d，如果d为0则为无向边，为1则为有向边。关于有向图和无向图的欧拉回路可以参考我的另一篇博文[ 欧拉通路欧拉

╰+哭是因爲堅強的太久メ/ 2022年08月25日 12:58/ 0 赞/ 54 阅读

相关 uva 1347——Tour

题意：给定n个点的坐标，设计一条路线，从左边的点出发，走到最右边的点然后返回，每个点除了起点和终点最多只能经历一次，求其中的最短路径。思路：dp，可以考虑成2个人

「爱情、让人受尽委屈。」/ 2022年08月14日 05:49/ 0 赞/ 30 阅读

相关 poj 2135 Farm Tour 【无向图最小费用最大流】

题目：[poj 2135 Farm Tour ][poj 2135 Farm Tour] 题意：给出一个无向图，问从 1 点到 n 点然后又回到一点总共的最短路。

约定不等于承诺〃/ 2022年08月13日 18:35/ 0 赞/ 222 阅读

相关启动Web Tours 服务

1、在默认安装完loadRunner的路径下找到StartServer.bat， ![Center][]

不念不忘少年蓝@/ 2022年07月16日 00:49/ 0 赞/ 233 阅读

相关 HDU 2677 Dota all stars 【dfs练习】

Dota all stars Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Ja

深藏阁楼爱情的钟/ 2022年06月05日 12:54/ 0 赞/ 167 阅读

相关 2677 4-1 复数类的运算符重载

4-1 复数类的运算符重载 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 通过本题目

短命女/ 2022年06月04日 03:18/ 0 赞/ 201 阅读

相关 HDU 5013 City Tour

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5013 题意： ![162233151122600.png][] 思路：

小鱼儿/ 2022年03月28日 01:58/ 0 赞/ 197 阅读

相关 POJ 2677 Tour

两个人同时从最左端出发，不会走相同的点，且出了起点和终点每个点恰好被一个人走一次，求到最右端的最小。用dp\[i\]\[j\] 表示快的人走到i 慢的人走到\[j\] 走

深碍√TFBOYSˉ_/ 2021年12月18日 14:29/ 0 赞/ 163 阅读

相关 POJ 1637 Sightseeing tour（混合图欧拉回路+最大流）

[http://poj.org/problem?id=1637][http_poj.org_problem_id_1637] 题意：给出n个点和m条边，这些边有些是单向

待我称王封你为后i/ 2021年09月29日 09:36/ 0 赞/ 277 阅读