1.具有代价的迷宫问题(Dijkstra算法+路径记录 HDU1026)

本题可视为权值为正（1-9实际上为1-10）的最短路径问题，因此使用Dijkstra算法求解。

普通Dijkstra算法维护两个数组，visited和dis，分别表示访问控制和最短距离。从起点出发，每次确定一个和起点距离最短的点，然后比较该点到其他未访问的点的距离，维护dis数组。直到所有点都确定，此时dis数组即为源点到各个点的距离。此为

教科书标准实现，时间复杂度 

优先队列优化版本：核心优化为把线性扫描遍历结点数组变为取小根堆的堆顶。

 就是自动排序的队列，配合合适的比较器，是 Dijkstra、TopK、哈夫曼等算法的核心数据结构。优先队列的显示结构为

priority_queue<int, vector<int>, less<int>> pq; 

其中第三个参数即为比较器，less（大根堆，默认）或greater（小根堆）。在使用自定义结构体时，需重构 < 或 >。 注意：比较器逻辑反直觉，

因为权值非负，由Dijkstra算法的特性可知，每次取出的都是最短距离，这样同时处理了访问控制和过期数据的问题。

注意：迷宫即图的问题是有可能出现过期数据的，

同一个格子可能通过不同路径到达

起点(0,0)要到达(2,2)：

路径A（绕远路）: (0,0)→(0,1)→(0,2)→(1,2)→(2,2)  代价=1+9+9+9=28
路径B（直接走）: (0,0)→(1,0)→(2,0)→(2,1)→(2,2)  代价=1+1+1+1=4


（距离28），之后发现路径B更短，

void dijkstra(priority_queue<Node, vector<Node>, greater<Node>> &priQ)

{
    // 初始时间为0
    time[0][0] = 0;
    // 起点入队
    priQ.push({time[0][0], 0, 0});
    while (!priQ.empty())
    {
        Node node = priQ.top();
        priQ.pop();
        int x = node.x, y = node.y;

        if (isChecked[x][y])
            continue;
        isChecked[x][y] = true;

        for (int i = 0; i < 4; i++)
        {
            //遍历四个方向
            int newX = x + direction[i].first;
            int newY = y + direction[i].second;
            if (newX < 0 || newX >= maze.size() || newY < 0 || newY >= maze[0].size() || maze[newX][newY] == 'X')
                continue;
            if (isChecked[newX][newY])
                continue;
            int newTime;
            // 代价计算
            if (maze[newX][newY] == '.')
                newTime = time[x][y] + 1;
            else
                newTime = time[x][y] + (maze[newX][newY] - '0') + 1;
            //小于当前点的最小距离则更新
            if (newTime < time[newX][newY])
            {
                time[newX][newY] = newTime;
                parent[newX][newY] = {x, y};
                priQ.push({newTime, newX, newY});
            }
        }
    }
}

当dijkstra算法执行完毕后，我们可以从终点不断访问直到起点路径。因此使用一个栈来使路径逆序，即从起点到终点。

stack<pair<int, int>> path;
            int x = n - 1, y = m - 1;
            while (x != -1 && y != -1)
            {
                path.push(make_pair(x, y));
                auto p = parent[x][y];
                x = p.first;
                y = p.second;
            }

用bfs和优先队列的Dijkstra算法的实现过程类似于从源点开始，慢慢向四周扩散更新最短距离，且优先走低代价区域。而单纯的bfs因为同权值，所以是四个方向同步推进，而优先队列方式会有快有慢。

所以，bfs只能处理无权值（或同权值）的单源最短路径问题而Dijkstra可以处理负权值的单源最短路径问题。

注意各数组的初始化以及输出格式。

#include <iostream>

#include <vector>

#include <queue>
#include <functional>
#include <stack>
using namespace std;

// 迷宫
vector<vector<char>> maze;
// 从起点到(x,y)点的最短距离
vector<vector<int>> time;
vector<vector<bool>> isChecked;
// 到达该点的上一个点
vector<vector<pair<int, int>>> parent;
vector<pair<int, int>> direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

struct Node
{
    int time, x, y;

    // 重载 > 用以构建优先队列小根堆
    bool operator>(const Node &other) const
    {
        return time > other.time;

    }
};

void dijkstra(priority_queue<Node, vector<Node>, greater<Node>> &priQ)
{
    // 初始时间为0
    time[0][0] = 0;
    // 起点入队

    priQ.push({time[0][0], 0, 0});
    while (!priQ.empty())
    {
        Node node = priQ.top();
        priQ.pop();
        int x = node.x, y = node.y;
        if (isChecked[x][y])
            continue;
        isChecked[x][y] = true;
        for (int i = 0; i < 4; i++)
        {
            int newX = x + direction[i].first;
            int newY = y + direction[i].second;
            if (newX < 0 || newX >= maze.size() || newY < 0 || newY >= maze[0].size() || maze[newX][newY] == 'X')
                continue;
            if (isChecked[newX][newY])
                continue;
            int newTime;
            // 代价计算
            if (maze[newX][newY] == '.')
                newTime = time[x][y] + 1;
            else
                newTime = time[x][y] + (maze[newX][newY] - '0') + 1;
            if (newTime < time[newX][newY])
            {
                time[newX][newY] = newTime;
                parent[newX][newY] = {x, y};
                priQ.push({newTime, newX, newY});
            }
        }
    }
}
int main()
{

    int n, m;

    while (cin >> n >> m)
    {
        maze.assign(n, vector<char>(m));
        time.assign(n, vector<int>(m, INT_MAX));
        parent.assign(n, vector<pair<int, int>>(m, {-1, -1}));
        isChecked.assign(n, vector<bool>(m, false));

        priority_queue<Node, vector<Node>, greater<Node>> priQ;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cin >> maze[i][j];

            }
        }

        dijkstra(priQ);
        if (time[n - 1][m - 1] == INT_MAX)
            cout << "God please help our poor hero." << endl;
        else
        {
            int currentTime = 1;
            cout << "It takes " << time[n - 1][m - 1];
            cout << " seconds to reach the target position, let me show you the way." << endl;
            stack<pair<int, int>> path;
            int x = n - 1, y = m - 1;
            while (x != -1 && y != -1)
            {
                path.push(make_pair(x, y));
                auto p = parent[x][y];
                x = p.first;
                y = p.second;
            }
            while (!path.empty() && currentTime <= time[n - 1][m - 1])
            {
                int nx = path.top().first;
                int ny = path.top().second;
                path.pop();
                if (maze[nx][ny] == '.' && !path.empty())
                {
                    cout << currentTime++ << "s:(" << nx << "," << ny << ")";
                    cout << "->";
                    cout << "(" << path.top().first << "," << path.top().second << ")" << endl;

                }
                else
                {
                    int duration = maze[nx][ny] - '0';
                    while (duration--)
                    {
                        cout << currentTime++ << "s:FIGHT AT " << "(" << nx << "," << ny << ")" << endl;
                    }
                    if (!path.empty())
                    {
                        cout << currentTime++ << "s:(" << nx << "," << ny << ")";
                        cout << "->";
                        cout << "(" << path.top().first << "," << path.top().second << ")" << endl;
                    }
                }
            }
        }
        cout << "FINISH" << endl;
    }

    return 0;
}

根据字典序的原则，降序为最大，所以我们从右往左查找时，找到的枢轴的右侧为一个降序序列即局部最大值记为S。序列的下一个排列是仅比当前序列大的排列。

已知枢轴右侧为局部最大值，因此我们要让当前序列增大的话，不应该改变S而应该改变枢轴的值且枢轴的左侧保持不变。如若改变了S，序列的值将会变小。而我们想要让这个序列增大的值尽可能地小，又S为降序序列，所以我们要从右往左找到第一个比枢轴大的数，这样保证了枢轴的位置增大的值最小。

记在S中找到的位置为X，交换后的S为S'。易知X的左侧大于等于枢轴，右侧一定小于枢轴（若等于则X就不是第一个了），因此S'仍然是一个降序序列，此时我们想要让S'最小即翻转S'。

考虑边界条件，当找不到升序序列，即为降序（最大值）时说明已经来到了最后一种排列。故我们需要翻转序列让其回到最小值。

这样我们增大了枢轴的值，又让右侧变为了最小，就得到了仅比当前排列大的下一个排列。

#include <iostream>

#include <string>

#include <vector>
#include <algorithm>
using namespace std;


void my_next_permutation(vector<int> &v)

{

    int len = v.size();
    if (len < 2)
    {
        return;

    }

    int pivot = -1;
    // 找到第一对升序序列
    for (int i = len - 2; i >= 0; i--)

    {
        if (v[i] < v[i + 1])
        {
            pivot = i;
            break;

        }
    }

    // 降序，即最大值，翻转回最小值（升序）
    if (pivot == -1)
    {
        reverse(v.begin(), v.end());
        return;
    }


    // 找到第一个比pivot大的数

    int Idx = len - 1;
    for (int i = len - 1; i > pivot; i--)
    {
        if (v[i] > v[pivot])
        {
            Idx = i;
            break;
        }
    }
    // 交换
    swap(v[pivot], v[Idx]);


    // 翻转
    reverse(v.begin() + pivot + 1, v.end());
}
int main()
{
    int n, m;

    while (cin >> n >> m)

    {
        vector<int> v;
        for (int i = 1; i <= n; i++)
        {
            v.push_back(i);
        }
        for (int i = 0; i < m - 1; i++)
        {

            my_next_permutation(v);
        }
        for (int i = 0; i < v.size(); i++)
        {
            cout << v[i];
            if (i != v.size() - 1)
                cout << " ";
        }
        cout << endl;
    }
    return 0;
}

完全背包问题：一个物品可以用无数次，凑出n。

用动态规划求解完全背包问题（二维数组实现）：

维护一个dp[i][j]表示总和为i的数最大部分不超过j的方案数。

;当总和为0时与最大数不超过1时的方案数都为1。

对于任意一个用 {1,2,...,j} 凑出 i 的方案，问一个问题：

所以总方案数 = 两种情况之和。

即最大部分超过总和时，方案数应为最大部分等于总和的方案数。

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    while (cin >> n)
    {
        // dp[i][j]表示总和为i，最大部分不超过j的方案数
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

        for (int i = 0; i <= n; i++)
        {
            // 总和为0的情况
            dp[0][i] = 1;
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (j > i)
                {
                    dp[i][j] = dp[i][i];
                }
                else
                {
                    // 不用j凑成i + 用j凑成i-j
                    dp[i][j] = dp[i][j - 1] + dp[i - j][j];
                }
            }
        }

        cout << dp[n][n] << endl;
    }

    return 0;
}

用动态规划求解完全背包问题（一维数组实现）（空间优化）：

维护一个dp[i]， dp[i]表示i有多少种分解方式。

for (int j = 1; j <= n; j++)
        {
            for (int i = j; i <= n; i++)
            {
                dp[i] += dp[i - j];
            }
        }

其中j表示目前最大可用的数，i为总和。这段代码的含义为：用{1,2…j}的数来凑出i。

j在外层的原因是：刻意构造强制非降序来保证不重复。

for i = 1 to 5:        // 当前要凑多少
    for j = 1 to i:    // 用一个数 j
        dp[i] += dp[i-j]


i=2, j=2: 用 2，剩 0 → 得到划分 [2]

i=3, j=2: 用 2，剩 1 → 凑 1 得到 [1] → 划分 [2,1]
          但 [2,1] 是降序！非法！
          
i=5, j=2: 用 2，剩 3 → 凑 3 时可以用 3 → 得到 [2,3]
i=5, j=3: 用 3，剩 2 → 凑 2 时可以用 2 → 得到 [3,2]

[2,3] 和 [3,2] 被算了两次！❌


✅ 正确顺序：最大部分 j 在外层

for j = 1 to 5:        // 当前最大允许用几
    for i = j to 5:    // 凑总和 i
        dp[i] += dp[i-j]


j=1: 只能用 1
     i=1: [1]
     i=2: [1,1]
     i=3: [1,1,1]
     ...全是 1

j=2: 可以用 1,2，但 2 是"新加入"的
     i=2: dp[2] += dp[0] = 1+1 = 2 → [1,1], [2]
     i=3: dp[3] += dp[1] = 1+1 = 2 → [1,1,1], [1,2]
     i=4: dp[4] += dp[2] = 1+2 = 3 → [1,1,1,1], [1,1,2], [2,2]
     i=5: dp[5] += dp[3] = 1+2 = 3 → [1,1,1,1,1], [1,1,1,2], [1,2,2]
     
     注意：所有含 2 的划分，2 都在后面！[1,2] 不是 [2,1] ✓

j=3: 可以用 1,2,3，3 是"新加入"的
     i=3: dp[3] += dp[0] = 2+1 = 3 → 新增 [3]
     i=4: dp[4] += dp[1] = 3+1 = 4 → 新增 [1,3]
     i=5: dp[5] += dp[2] = 3+2 = 5 → 新增 [2,3], [1,1,3]
     
     注意：[2,3] 不是 [3,2]！因为 j=2 阶段已经过了，不会再产生 2 在 3 后的情况！

考虑边界条件 dp [0] = 1，即总和为0时只有一种方法，那就是什么都不选。

当j = 1时，dp[1~n]都=1，dp[1] += dp[0] = 1;

当j = 2时，所有总和小于2的都会被确定，此时dp[3] += dp[1]，因为dp[1]已经被确定，从而dp[3]也会被确定.

当j = 3时，所有总和小于3的都会被确定，……

从而我们可以得出，正序遍历 i，计算 dp[i] 时，dp[i-j] 已经确定，从而从小到大递推求解。

关键观察：以 "是否包含 j" 分类

3. 剩余部分仍然可以用 {1, 2, ..., j}（因为 j 可以重复使用）

不用 j 的方案数 + 至少用一个 j 的方案数

dp[i]（旧值）+ dp[i-j]  即：dp[i] += dp[i-j]

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    while (cin >> n)
    {
        // dp[i]表示i有多少种分解方式
        vector<int> dp(n + 1, 0);

        // 什么都不选
        dp[0] = 1;
        for (int j = 1; j <= n; j++)
        {
            for (int i = j; i <= n; i++)
            {
                dp[i] += dp[i - j];
            }
        }

        cout << dp[n] << endl;
    }

    return 0;
}

Coding day8

算法

编程语言

Dijkstra算法解决迷宫最短路径问题，通过优先队列优化实现高效搜索。文章详解了路径记录、过期数据处理及代码实现，同时对比了BFS与Dijkstra的区别。还包含字典序排列和完全背包问题的动态规划解法，提供清晰的算法思路和AC代码示例。

数据结构

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

Coding day8

Coding day8

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐