当前位置: 首页 > news >正文

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;elsestd::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";elsestd::cout<<dist[t]<<"\n";}return 0;
}

http://www.lryc.cn/news/301165.html

相关文章:

  • 交通管理|交通管理在线服务系统|基于Springboot的交通管理系统设计与实现(源码+数据库+文档)
  • 最适合初学者的Python入门详细攻略,一文讲清,赶紧收藏!
  • 幻兽帕鲁新手游戏攻略分享
  • 代码随想录算法训练营DAY19 | 二叉树 (6)
  • 【C++】实现Date类的各种运算符重载
  • 【Linux】程序地址空间 -- 详解 Linux 2.6 内核进程调度队列 -- 了解
  • 10-通用类型、特质和生命周期
  • STM32CubeMX,定时器之定时功能,入门学习,如何设置prescaler,以及timer计算PWM输入捕获方法(重要)
  • 蓝桥杯:C++队列、优先队列、链表
  • 【C语言】长篇详解,字符系列篇1-----“混杂”的各种字符类型字符转换和strlen的模拟实现【图文详解】
  • 2024年【高处安装、维护、拆除】考试总结及高处安装、维护、拆除考试技巧
  • 开源无处不在,发展创新下又有何弊端
  • LeetCode 0429.N 叉树的层序遍历:广度优先搜索(BFS)
  • Practical User Research for Enterprise UX
  • 文生视频:Sora模型报告总结
  • GA 374-2019 电子防盗锁检测
  • 代码随想录day26 Java版
  • 英文论文(sci)解读复现【NO.21】一种基于空间坐标的轻量级目标检测器无人机航空图像的自注意
  • 数据集合
  • php基础学习之作用域和静态变量
  • SP1:基于Plonky3构建的zkVM
  • Python爬虫之文件存储#5
  • Spring Boot 笔记 012 创建接口_添加文章分类
  • Spring-面试题
  • Flink理论—容错之状态
  • 【数据结构】链表OJ面试题5《链表的深度拷贝》(题库+解析)
  • 智慧校园规划建设方案
  • 003 - Hugo, 创建文章
  • HCIA-HarmonyOS设备开发认证V2.0-IOT硬件子系统-GPIO
  • 《Java 简易速速上手小册》第7章:Java 网络编程(2024 最新版)