2024/2/17 图论 最短路入门 dijkstra 1

目录

算法思路

Dijkstra求最短路

AcWing 849. Dijkstra求最短路 I - AcWing

850. Dijkstra求最短路 II - AcWing题库

最短路

最短路 - HDU 2544 - Virtual Judge (vjudge.net)

【模板】单源最短路径（弱化版）

P3371 【模板】单源最短路径（弱化版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

【模板】单源最短路径（标准版）

P4779 【模板】单源最短路径（标准版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

畅通工程续

 畅通工程续 - HDU 1874 - Virtual Judge (vjudge.net)

算法思路

dijkstra解决的是单源的最短路问题，就是一个顶点到其他顶点的最短路问题

开一个数组dist,dist[x]表示从起点出发，到x的距离

比如这幅图，初始情况下，把所有的dist都设置为inf（也就是无穷大）

dist[1]=0,dist[2]=dist[3]=inf

因为1是起点，自己到自己的距离是0

还有一个bool类型的vis数组，因为每个点只能走一次

选当前离起点最近（权值最小）且没有选过的点，来更新其它点的距离

所以如图：

第一次选1号，更新最近的2，3号点 dist[2]=2,dist[3]=4

第二次选2号（因为权值比1到3的小）  dist[2]+1<dist[3],所以dist[3]=dist[2]+1

这个样例的最短路就得到了

Dijkstra求最短路

AcWing 849. Dijkstra求最短路 I - AcWing

850. Dijkstra求最短路 II - AcWing题库

这两道题只有数据范围的差别，用下面的代码可以一次过

注意：

优先队列q里面的pair存的是dist和点数

二维数组g里面的pair存的是点数和边权

完整代码:

#include <bits/stdc++.h>
#define int long long
const int N = 15e4+10;
std::vector<std::vector<std::pair<int,int>>> g(N);
#define PII std::pair<int,int>
signed main()
{
    int n,m;
    std::cin >> n >> m;
    for(int i = 1;i <= m;i ++)
    {
        int u,v,w;
        std::cin >> u >> v >> w;
        g[u].push_back({v,w});
    }
    std::priority_queue<PII,std::vector<PII>,std::greater<>> q;
    std::vector<int> dist(n+1,INT_MAX);
    std::vector<bool> vis(n+1);
    dist[1]=0;
    q.push({0,1});//存dist和点数
    while(!q.empty())
    {
        auto node = q.top();
        q.pop();
        int cur=node.second;
        if(vis[cur]==true)
            continue;
        else
        {
            vis[cur]=true;
            for(int i = 0;i < g[cur].size();i ++)
            {
                int e=g[cur][i].first;
                int w=g[cur][i].second;
                if(dist[e]>dist[cur]+w)
                {
                    dist[e]=dist[cur]+w;
                    q.push({dist[e],e});
                }
            }
        }
    }
    if(dist[n]==INT_MAX)
        std::cout<<-1;
    else
        std::cout<<dist[n];
    return 0;
}

最短路

最短路 - HDU 2544 - Virtual Judge (vjudge.net)

思路：dijkstra，但是需要建立双向边

注意：多组输入最好不要开全局变量，如果开全局变量记得清空

完整代码：

#include <bits/stdc++.h>
#define int long long
#define PII std::pair<int,int>
const int N = 1e4+10;
signed main()
{
    int n,m;
    while(std::cin >> n >> m)
    {
        if(n==0&&m==0)
            break;
        std::vector<std::vector<std::pair<int,int>>>g (N+1);
        std::priority_queue<PII,std::vector<PII>,std::greater<>> q;
        std::vector<int> dist(n+1,INT_MAX);
        std::vector<bool> vis(n+1);
        dist[1]=0;
        for(int i = 1;i <= m;i ++)
        {
            int u,v,w;
            std::cin >> u >> v >> w;
            g[u].push_back({v,w});
            g[v].push_back({u,w});
        }
        q.push({0,1});//存dist和点数
        while(!q.empty()) {
            auto node = q.top();
            q.pop();
            int cur = node.second;
            if (vis[cur] == true)
                continue;
            else {
                vis[cur] = true;
                for (int i = 0; i < g[cur].size(); i++) {
                    int e = g[cur][i].first;//存点
                    int w = g[cur][i].second;//存边权
                    if (dist[e] > dist[cur] + w) {
                        dist[e] = dist[cur] + w;
                        q.push({dist[e], e});
                    }
                }
            }
        }
        std::cout<<dist[n]<<"\n";
    }
    return 0;
}

【模板】单源最短路径（弱化版）

P3371 【模板】单源最短路径（弱化版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：dijkstra模板

完整代码：

#include <bits/stdc++.h>
#define int long long
#define PII std::pair<int,int>
const int N = 5e5+10;
signed main()
{
    int n,m,s;
    std::cin >> n >> m >> s;
    std::vector<std::vector<std::pair<int,int>>> g(n+1);
    std::vector<int> dist(n+1,INT_MAX);
    std::vector<bool> vis(n+1);
    dist[s]=0;
    for(int i = 1; i <= m;i ++)
    {
        int u,v,w;
        std::cin >> u >> v >> w;
        g[u].push_back({v,w});
    }
    std::priority_queue<PII,std::vector<PII>,std::greater<>> q;
    q.push({0,s});//存dist和点数
    while(!q.empty()) {
        auto node = q.top();
        q.pop();
        int cur = node.second;
        if (vis[cur] == true)
            continue;
        else {
            vis[cur] = true;
            for (int i = 0; i < g[cur].size(); i++) {
                int e = g[cur][i].first;//存点
                int w = g[cur][i].second;//存边权
                if (dist[e] > dist[cur] + w) {
                    dist[e] = dist[cur] + w;
                    q.push({dist[e], e});
                }
            }
        }
    }
    for(int i = 1;i <= n;i ++)
    {
        std::cout<<dist[i]<<" ";
    }
    return 0;
}

【模板】单源最短路径（标准版）

P4779 【模板】单源最短路径（标准版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

和上一题的代码一样，只是数据范围大一点

完整代码：

#include <bits/stdc++.h>
#define int long long
#define PII std::pair<int,int>
const int N = 5e5+10;
signed main()
{
    int n,m,s;
    std::cin >> n >> m >> s;
    std::vector<std::vector<std::pair<int,int>>> g(n+1);
    std::vector<int> dist(n+1,INT_MAX);
    std::vector<bool> vis(n+1);
    dist[s]=0;
    for(int i = 1; i <= m;i ++)
    {
        int u,v,w;
        std::cin >> u >> v >> w;
        g[u].push_back({v,w});
    }
    std::priority_queue<PII,std::vector<PII>,std::greater<>> q;
    q.push({0,s});//存dist和点数
    while(!q.empty()) {
        auto node = q.top();
        q.pop();
        int cur = node.second;
        if (vis[cur] == true)
            continue;
        else {
            vis[cur] = true;
            for (int i = 0; i < g[cur].size(); i++) {
                int e = g[cur][i].first;//存点
                int w = g[cur][i].second;//存边权
                if (dist[e] > dist[cur] + w) {
                    dist[e] = dist[cur] + w;
                    q.push({dist[e], e});
                }
            }
        }
    }
    for(int i = 1;i <= n;i ++)
    {
        std::cout<<dist[i]<<" ";
    }
    return 0;
}

畅通工程续

 畅通工程续 - HDU 1874 - Virtual Judge (vjudge.net)

思路：用dijkstra，双向建边

完整代码：

#include <bits/stdc++.h>
#define int long long
#define PII std::pair<int,int>
signed main()
{
    int n,m;
    while(std::cin >> n >> m)
    {
        std::vector<std::vector<PII>>g(n+1);
        std::vector<int> dist(n+1,INT_MAX);
        std::vector<bool> vis(n+1);
        std::priority_queue<PII,std::vector<PII>,std::greater<>> q;
        for(int i = 1;i <= m;i ++)
        {
            int u,v,w;
            std::cin >> u >> v >> w;
            g[u].push_back({v,w});
            g[v].push_back({u,w});
        }
        int s,t;
        std::cin >> s >> t;
        dist[s]=0;
        q.push({0,s});//存dist和点数
        while(!q.empty())
        {
            auto node = q.top();
            q.pop();
            int cur=node.second;
            if(vis[cur]==true)
                continue;
            vis[cur]=true;
            for(int i = 0;i < g[cur].size();i ++)
            {
                int e=g[cur][i].first;
                int w=g[cur][i].second;
                if(dist[e]>dist[cur]+w)
                {
                    dist[e]=dist[cur]+w;
                    q.push({dist[e],e});
                }
            }
        }
        if(dist[t]==INT_MAX)
            std::cout<<-1<<"\n";
        else
            std::cout<<dist[t]<<"\n";
    }
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/391307.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

echarts制作两个柱状图

echarts制作两个柱状图

let colorList[#02ce8b,#ffbe62,#f17373]; let data1 [90,80,70,50] option { title:[{ // 第一个标题text: 环保检测, // 主标题textStyle: { // 主标题样式color: #333,fontWeight: bold,fontSize: 16},left: 20%, // 定位到适合的位置top: 10%, // 定位到适合的位置},{ //…
阅读更多...
【plt.scatter绘制散点图】：从入门到精通，只需一篇文章！【Matplotlib】

【plt.scatter绘制散点图】：从入门到精通，只需一篇文章！【Matplotlib】

【plt.scatter绘制散点图】&#xff1a;从入门到精通&#xff0c;只需一篇文章&#xff01;【Matplotlib】&#xff01;&#x1f680; 利用Matplotlib进行数据可视化示例 &#x1f335;文章目录&#x1f335; 一、plt.scatter入门&#xff1a;轻松迈出第一步 &#x1f463;二、…
阅读更多...
各类电纸书使用体验

各类电纸书使用体验

对移动阅读一直有着强烈的愿望&#xff0c;想要一个易于携带&#xff0c;又能看着比较大气的电子阅读器&#xff0c;这是一个矛盾...所以现在用着海信Hi Reader Pro&#xff0c;还想再寻找一个合适的家用阅读器&#xff0c;对自己用过的阅读器总结一下&#xff0c;给大家做个参…
阅读更多...
图像卷积、步长、填充、特征图、多通道卷积、权重共享、感受野、池化

图像卷积、步长、填充、特征图、多通道卷积、权重共享、感受野、池化

图像卷积、步长、填充、特征图、多通道卷积、权重共享、感受野、池化 卷积神经网络的一些基本概念&#xff1a;图像卷积、步长、填充、特征图、多通道卷积、权重共享、感受野、池化 1.图像卷积、步长、填充 图像卷积&#xff1a;卷积核矩阵在一个原始图像矩阵上 “从上往下、…
阅读更多...
XUbuntu22.04之apt与snap如何重装软件(二百一十二)

XUbuntu22.04之apt与snap如何重装软件(二百一十二)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…
阅读更多...
Vue2学习第二天

Vue2学习第二天

Vue2 学习第二天 1. 数据绑定 Vue 中有 2 种数据绑定的方式&#xff1a; 单向绑定(v-bind)&#xff1a;数据只能从 data 流向页面。双向绑定(v-model)&#xff1a;数据不仅能从 data 流向页面&#xff0c;还可以从页面流向 data。 备注&#xff1a; 双向绑定一般都应用在表单…
阅读更多...
比特币 P2PKH、P2SH

比特币 P2PKH、P2SH

标准脚本P2PKH、P2SH 区块链重要基础知识7-1——标准脚本P2PKH、P2SH-CSDN博客 比特币中P2SH(pay-to-script-hash)多重签名的锁定脚本和解锁脚本 https://www.cnblogs.com/itlgl/p/10419325.html
阅读更多...
Python算法题集_将有序数组转换为二叉搜索树

Python算法题集_将有序数组转换为二叉搜索树

Python算法题集_将有序数组转换为二叉搜索树 题108&#xff1a;将有序数组转换为二叉搜索树1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【极简代码递归】2) 改进版一【多行代码递归】3) 改进版二【极简代码递归传递下标】 4. 最优算法 本文为…
阅读更多...
StarRocks表设计——分区分桶与副本数

StarRocks表设计——分区分桶与副本数

目录 一、数据分布 1.1 概述 1.2 数据分布方式 1.2.1 Round-Robin 1.2.2 Range 1.2.3 List 1.2.4 Hash 1.3 StarRocks的数据分布方式 1.3.1 不分区 Hash分桶 1.3.2 Range分区Hash分桶 三、分区 3.1 分区概述 3.2 创建分区 3.2.1 手动创建分区 3.2.2 批量创建分区…
阅读更多...
Stable Diffusion系列（五）：原理剖析——从文字到图片的神奇魔法（扩散篇）

Stable Diffusion系列（五）：原理剖析——从文字到图片的神奇魔法（扩散篇）

文章目录 DDPM论文整体原理前向扩散过程反向扩散过程模型训练过程模型生成过程概率分布视角参数模型设置论文结果分析 要想完成SD中从文字到图片的操作&#xff0c;必须要做到两步&#xff0c;第一步是理解文字输入包含的语义&#xff0c;第二步是利用语义引导图片的生成。下面…
阅读更多...
String讲解

String讲解

文章目录 String类的重要性常用的方法常用的构造方法String类的比较字符串的查找转化数字转化为字符串字符串转数字 字符串替换字符串的不可变性 字符串拆分字符串截取字符串修改 StringBuilder和StringBuffer String类的重要性 在c/c的学习中我们接触到了字符串&#xff0c;但…
阅读更多...
阿里（淘天）一面笔试算法原题

阿里（淘天）一面笔试算法原题

阿里撤资 "车来了" 近日&#xff0c;国内实时公交产品"车来了"关联公司武汉元光科技有限公司发生工商变更&#xff0c;阿里巴巴&#xff08;中国&#xff09;网络技术有限公司退出股东行列。 这很好理解&#xff0c;符合近期阿里收缩战线的行为一致性。 毕…
阅读更多...
自然语言编程系列（四）：GPT-4对编程开发的支持

自然语言编程系列（四）：GPT-4对编程开发的支持

在编程开发领域&#xff0c;GPT-4凭借其强大的自然语言理解和代码生成能力&#xff0c;能够深刻理解开发者的意图&#xff0c;并基于这些需求提供精准的编程指导和解决方案。对于开发者来说&#xff0c;GPT-4能够在代码片段生成、算法思路设计、模块构建和原型实现等方面给予开…
阅读更多...
【大厂AI课学习笔记】【2.1 人工智能项目开发规划与目标】（2）项目开发周期

【大厂AI课学习笔记】【2.1 人工智能项目开发规划与目标】（2）项目开发周期

我们来学习项目开发的周期。 再次声明&#xff0c;本文来自腾讯AI课的学习笔记&#xff0c;图片和文字&#xff0c;仅用于大家学习&#xff0c;想了解更多知识&#xff0c;请访问腾讯云相关章节。如果争议&#xff0c;请联系作者。 今天&#xff0c;我们来学习AI项目的周期。 主…
阅读更多...
跟着pink老师前端入门教程（JavaScript）-day03

跟着pink老师前端入门教程（JavaScript）-day03

四、数据类型 &#xff08;一&#xff09;数据类型简介 1、为什么需要数据类型 在计算机中&#xff0c;不同的数据所需占用的存储空间是不同的&#xff0c;为了便于把数据分成所需内存大小不同的数据&#xff0c;充分利用存储空间&#xff0c;于是定义了不同的数据类型。 …
阅读更多...
python实现多图绘制系统

python实现多图绘制系统

文章目录 需求和框架AxisFrameAxisListDarwSystem 从零开始实现一个三维绘图系统 需求和框架 本文希望实现下图所示的绘图系统&#xff0c;下面详细分析需求变化。 和之前实现的绘图系统相比&#xff0c;首先是多了【新增】和【删除】这两个按钮&#xff0c;其功能是控制绘图数…
阅读更多...
spring boot3登录开发-2(1图形验证码接口实现)

spring boot3登录开发-2(1图形验证码接口实现)

⛰️个人主页: 蒾酒 &#x1f525;系列专栏&#xff1a;《spring boot实战》 &#x1f30a;山高路远&#xff0c;行路漫漫&#xff0c;终有归途。 目录 前置条件 内容简介 图形验证码接口实现 导入糊涂工具依赖 接口分析 编写验证码接口 测试验证码接口 前置条件 …
阅读更多...
【Python---六大数据结构】

【Python---六大数据结构】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;Python &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; Python---六大数据结构 往期内容前言概述一下可变与不可变 Number四种不同的数值类型Number类型的创建i…
阅读更多...
一、ActiveMQ介绍

一、ActiveMQ介绍

ActiveMQ介绍 一、JMS1.jms介绍2.jms消息传递模式3.JMS编码总体架构 二、消息中间件三、ActiveMQ介绍1.引入的原因1.1 原因1.2 遇到的问题1.3 解决思路 2.定义3.特点3.1 异步处理3.2 应用系统之间解耦3.3 实际-整体架构 4.作用 一、JMS 1.jms介绍 jms是java消息服务接口规范&…
阅读更多...
Android安卓架构MVC、MVP、MVVM模式的概念与区别

Android安卓架构MVC、MVP、MVVM模式的概念与区别

目录 MVC框架 MVP框架 MVVM框架 MVVM与MVP区别 MVVM与MVC区别 MVC、MVP、MVVM模式哪个要好一些 MVC&#xff08;Model-View-Controller&#xff09;、MVP&#xff08;Model-View-Presenter&#xff09;、MVVM&#xff08;Model-View-ViewModel&#xff09;是三种常见的软…
阅读更多...
最新文章

Copyright @ 2022~2023