AOJ 2200 Mr. Rito Post Office 最短路径+动态规划+谨慎+思维

这篇具有很好参考价值的文章主要介绍了AOJ 2200 Mr. Rito Post Office 最短路径+动态规划+谨慎+思维。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

我写了好多注释,一看就能看懂,这个题目我想了6,7个小时,一开始忽略了船的位置和要把船安置的位置一致的情况,补上就对了。文章来源地址https://www.toymoban.com/news/detail-624498.html

#include <iostream>
using namespace std;
int inf = 0x3f3f3f3f, num[1007], dp[1007][207], L[207][207], S[207][207], N, M, R;
void init()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            L[i][j] = inf;
            S[i][j] = inf;
        }
        L[i][i] = 0;
        S[i][i] = 0;
    }
}
void input()
{
    int from, to, cost;
    char op;
    for (int i = 1; i <= M; i++)
    {
        scanf("%d %d %d %c\n", &from, &to, &cost, &op);
        if (op == 'S')
        {
            if (cost < S[from][to])
            {
                S[from][to] = cost;
            }
            if (cost < S[to][from])
            {
                S[to][from] = cost;
            }
        }
        else if (op == 'L')
        {
            if (cost < L[from][to])
            {
                L[from][to] = cost;
            }
            if (cost < L[to][from])
            {
                L[to][from] = cost;
            }
        }
    }
    scanf("%d", &R);
    for (int i = 1; i <= R; i++)
    {
        scanf("%d", &num[i]);
    }
}
void floyd()
{
    for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (L[i][k] != inf && L[k][j] != inf)
                {
                    if (L[i][k] + L[k][j] < L[i][j])
                    {
                        L[i][j] = L[i][k] + L[k][j];
                    }
                }
                if (S[i][k] != inf && S[k][j] != inf)
                {
                    if (S[i][k] + S[k][j] < S[i][j])
                    {
                        S[i][j] = S[i][k] + S[k][j];
                    }
                }
            }
        }
    }
}
void handleNormalLine(int i, int j)
{
    // dp[i][j]是从num[1]到达num[i],并且到达num[i]时船在j的最小路径,当i大于1时,dp[i][j]一定与num[i-2]走到num[i-1]时停船的位置有关
    // 我们需要从num[i-1]走陆路到k,然后走水路到j,把船停在j,之后走陆路从j到num[i]
    dp[i][j] = inf;
    for (int k = 1; k <= N; k++)
    {
        if (k != j)
        {
            // 从num[i-1]到k的陆路不通,从k到j的水路不通,从j到num[i]的陆路不通,从1到num[i-1]并且停船到k实现不了,那么这种情况不用计算
            if (L[num[i - 1]][k] == inf || S[k][j] == inf || L[j][num[i]] == inf || dp[i - 1][k] == inf)
            {
                continue;
            }
            if (L[num[i - 1]][k] + S[k][j] + L[j][num[i]] + dp[i - 1][k] < dp[i][j])
            {
                dp[i][j] = L[num[i - 1]][k] + S[k][j] + L[j][num[i]] + dp[i - 1][k];
            }
        }
        else
        {
            // k和j相等时,就不需要走陆路到k,然后再走水路到j了,直接从num[i-1]走陆路到num[i]即可,因为j==k船已经在j了,不用管船
            if (L[num[i - 1]][num[i]] == inf || dp[i - 1][k] == inf)
            {
                continue;
            }
            if (L[num[i - 1]][num[i]] + dp[i - 1][k] < dp[i][j])
            {
                dp[i][j] = L[num[i - 1]][num[i]] + dp[i - 1][k];
            }
        }
    }
}
void handleFirstLine(int i, int j)
{
    // i=1时,船就在num[i],dp[i][j] i=1 代表开船到j,船放在j,然后陆路走回来num[i]
    // 走水路开船从num[i]到j,然后船停在j,之后从j走陆路回到num[i],如果num[i]到j的水路,或者j到num[i]的陆路不通,那么这个都无法实现
    if (S[num[i]][j] == inf || L[j][num[i]] == inf)
    {
        dp[i][j] = inf;
        return;
    }
    dp[i][j] = S[num[i]][j] + L[j][num[i]];
}
void doDp()
{
    // 我们用dp[i][j] 代表邮递员从 num[1]按照顺序一个个走到num[i],即达到邮递员在num[i]且船的位置在j的状态下,最小的消耗
    for (int i = 1; i <= R; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (i == 1)
            {
                handleFirstLine(i, j);
            }
            else
            {
                handleNormalLine(i, j);
            }
        }
    }
}
int findAns()
{
    int ans = inf;
    for (int i = 1; i <= N; i++)
    {
        if (dp[R][i] < ans)
        {
            ans = dp[R][i];
        }
    }
    return ans;
}
int main()
{
    while (true)
    {
        scanf("%d%d", &N, &M);
        if (N == 0 && M == 0)
        {
            break;
        }
        init();
        input();
        floyd();
        doDp();
        printf("%d\n", findAns());
    }
    return 0;
}

到了这里,关于AOJ 2200 Mr. Rito Post Office 最短路径+动态规划+谨慎+思维的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【动态规划】多段图最短路径(动图演示)

    📃个人主页:个人主页 🔥系列专栏:数据结构与算法 💬推荐一款模拟面试、刷题神器,从基础到大厂面试题👉点击跳转刷题网站进行注册学习 写在前面: 多段图是一个有向的无环图。求解从起始点v0到终止点的最短路径的长度, 首先看一下这个问题是否具有最优子结构

    2023年04月08日
    浏览(26)
  • Python 动态规划 实现机器人躲避障碍物获取最短路径

    要设计一种算法来寻找机器人从左上角移动到右下角的路径,可以使用动态规划来解决这个问题。下面是一种可能的算法: 创建一个处理机器人运动的函数 find_path ,函数接受一个矩阵 grid 作为参数,用于表示机器人移动的网格环境,该矩阵一个由 0 和 1 组成的二位列表,其

    2024年04月09日
    浏览(47)
  • 【动态规划】【广度优先搜索】【状态压缩】847 访问所有节点的最短路径

    视频算法专题 动态规划汇总 广度优先搜索 状态压缩 存在一个由 n 个节点组成的无向连通图,图中的节点按从 0 到 n - 1 编号。 给你一个数组 graph 表示这个图。其中,graph[i] 是一个列表,由所有与节点 i 直接相连的节点组成。 返回能够访问所有节点的最短路径的长度。你可

    2024年01月23日
    浏览(41)
  • 【线性规划】基于python的最短路径线性规划

    前言 1. 案例介绍 2. 整数规划模型构建 2.1. 梳理模型思路 2.2. 构建自变量 2.3. 构建目标函数 2.4. 构建约束条件 3. 基于Python+Pulp求解实现 3.1. 构建有向图处理类 3.2. 建立整数规划模型 3.3. 带入案例中的有向图数据 3.4. 查看最优路径 最短路问题(shortest path problem, SSP)是图论的经

    2024年02月13日
    浏览(41)
  • 【路径规划】鲸鱼算法栅格地图机器人最短路径规划【含Matlab源码 3613期】

    1 鲸鱼算法 一种元启发式优化算法,模拟座头鲸狩猎行为的元启发式优化算法。目前的工作与其他群优化算法相比的主要区别在于,采用随机或最佳搜索代理来模拟捕猎行为,并使用螺旋来模拟座头鲸的泡泡网攻击机制。该算法具有机制简单、参数少、寻优能力强等优点,在

    2024年02月04日
    浏览(60)
  • 【路径规划】萤火虫算法栅格地图机器人最短路径规划【含Matlab源码 3662期】

    ✅博主简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,Matlab项目合作可私信。 🍎个人主页:海神之光 🏆代码获取方式: 海神之光Matlab王者学习之路—代码获取方式 ⛳️座右铭:行百里者,半于九十。 更多Matlab仿真内容点击👇 Matlab图像处理(进阶版) 路径规划

    2024年02月20日
    浏览(105)
  • 【路径规划】自适应遗传算法机器人栅格地图最短路径规划【含Matlab源码 3570期】

    1 遗传算法 遗传算法是一种基于生物进化论模型的优化算法,通过模拟生物进化的过程,通过复制、交叉、突变等操作产生下一代的解,并逐步淘汰掉适应度函数值低的解,增加适应度函数值高的解。遗传算法可以用于解决各种优化问题,如函数优化、组合优化、机器学习等

    2024年02月03日
    浏览(80)
  • 【路径规划】(2) A* 算法求解最短路,附python完整代码

    大家好,今天和各位分享一下机器人路径规划中非常经典的 A* 算法,感兴趣的点个关注,文末有 python 代码,那我么开始吧。 A* 算法是 1968 年 P.E.Hart[1]等人所提出的 在全局地图环境中所有已知情形下求解最短路径问题的方法,由于其简洁高效,容易实施 等 优点 而受到人们

    2024年02月03日
    浏览(36)
  • 【路径规划】(1) Dijkstra 算法求解最短路,附python完整代码

    好久不见,我又回来了, 这段时间把路径规划的一系列算法整理一下 ,感兴趣的点个关注。今天介绍一下机器人路径规划算法中最基础的 Dijkstra 算法,文末有 python 完整代码,那我们开始吧。 1959 年,荷兰计算机科学家 ·EdsgerWybe·Dijkstra 发表了论文《 A note on two problems in c

    2023年04月08日
    浏览(49)
  • 【路径规划】基于matlab火鹰算法栅格地图机器人最短路径规划【含Matlab源码 3679期】

    ✅博主简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,Matlab项目合作可私信。 🍎个人主页:海神之光 🏆代码获取方式: 海神之光Matlab王者学习之路—代码获取方式 ⛳️座右铭:行百里者,半于九十。 更多Matlab仿真内容点击👇 Matlab图像处理(进阶版) 路径规划

    2024年02月02日
    浏览(58)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包