基础算法——搜索与图论
搜索与图论
- 图的存储方式
- 2、最短路问题
- 2.1、Dijkstra算法(朴素版)
- 2.2、Dijkstra算法(堆优化版)
- 2.3、Bellman-Ford算法
- 2.4、SPFA求最短路
- 2.5、SPFA判负环
- 2.6、Floyd算法
图的存储方式

2、最短路问题
最短路问题可以分为单源最短路问题和多源最短路问题,单源最短路问题就是求出从点1->n的最短距离,而多源最短路问题就是求出从点i->j的最短距离。单源最短路问题还可以分为正权边的单源最短路问题和负权边的单源最短路问题。具体算法和时间复杂度如下图:

2.1、Dijkstra算法(朴素版)

算法模板:
#include <iostream>
#include <cstring>using namespace std;
const int N = 510;
int g[N][N], d[N];
int n, m;
bool st[N];int dijkstra()
{memset(d, 0x3f, sizeof d);d[1] = 0;for (int i = 0; i < n; i++){int t = -1;for (int j = 1; j <= n; j++)if (!st[j] && (t == -1 || d[t] > d[j]))t = j;st[t] = true;for (int j = 1; j <= n; j++)d[j] = min(d[j], d[t] + g[t][j]);}return d[n] == 0x3f3f3f3f ? -1 : d[n];
}int main()
{cin >> n >> m;memset(g, 0x3f, sizeof g);while (m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);g[a][b] = min(g[a][b], c);}cout << dijkstra() << endl;return 0;
}
2.2、Dijkstra算法(堆优化版)
下面来看看如何优化:

算法模板:
#include <iostream>
#include <cstring>
#include <queue>using namespace std;
typedef pair<int, int> PII;
const int N = 1.5e5+10;
int h[N], e[N], w[N], ne[N], idx;
int n, m, d[N];
bool st[N];void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}int dijkstra()
{memset(d, 0x3f, sizeof d);d[1] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, 1});while (heap.size()){auto t = heap.top();heap.pop();int ver = t.second, dis = t.first;if (st[ver]) continue;st[ver] = true;for (int i = h[ver]; i != -1; i = ne[i]){int j = e[i];if (d[j] > dis + w[i]){d[j] = dis + w[i];heap.push({d[j], j});}}}return d[n] == 0x3f3f3f3f ? -1 : d[n];
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);while (m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}cout << dijkstra() << endl;return 0;
}
2.3、Bellman-Ford算法

代码模板:
#include <iostream>
#include <cstring>using namespace std;
const int N = 510, M = 10010;
int n, m, k;
int d[N], backup[N];struct Edge
{int a, b, w;
}edges[M];void bellman_ford()
{memset(d, 0x3f, sizeof d);d[1] = 0;for (int i = 0; i < k; i++){memcpy(backup, d, sizeof d);for (int j = 0; j < m; j++){auto e = edges[j];d[e.b] = min(d[e.b], backup[e.a] + e.w);}}
}int main()
{cin >> n >> m >> k;for (int i = 0; i < m; i++){int a, b, w;scanf("%d%d%d", &a, &b, &w);edges[i] = {a, b, w};}bellman_ford();if (d[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;else cout << d[n] << endl;return 0;
}
2.4、SPFA求最短路

代码模板:
#include <iostream>
#include <cstring>
#include <queue>using namespace std;
const int N = 1e5+10;
int n, m;
int h[N], e[N], w[N], ne[N], idx;
int d[N];
bool st[N];void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}void spfa()
{memset(d, 0x3f, sizeof d);d[1] = 0;queue<int> q;q.push(1);st[1] = true;while (q.size()){auto t = q.front();q.pop();st[t] = false;for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (d[j] > d[t] + w[i]){d[j] = d[t] + w[i];if (!st[j]){st[j] = true;q.push(j);}}}}
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);while (m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}spfa();if (d[n] == 0x3f3f3f3f) cout << "impossible" << endl;else cout << d[n] << endl;return 0;
}
2.5、SPFA判负环

#include <iostream>
#include <cstring>
#include <queue>using namespace std;
const int N = 2010, M = 10010;
int h[N], e[M], w[M], ne[M], idx;
int n, m;
int d[N], cnt[N];
bool st[N];void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}bool spfa()
{queue<int> q;for (int i = 1; i <= n; i++){q.push(i);st[i] = true;}while (q.size()){auto t = q.front();q.pop();st[t] = false;for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (d[j] > d[t] + w[i]){d[j] = d[t] + w[i];cnt[j] = cnt[t] + 1;if (cnt[j] >= n) return true;if (!st[j]){st[j] = true;q.push(j);}}}}return false;
}int main()
{cin >> n >> m;memset(h, -1, sizeof h);while (m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}if (spfa()) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}
2.6、Floyd算法

#include <iostream>
#include <cstring>using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int d[N][N];
int n, m, k;void floyd()
{for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}int main()
{cin >> n >> m >> k;for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)if (i == j) d[i][j] = 0;else d[i][j] = INF;while (m--){int a, b, c;cin >> a >> b >> c;d[a][b] = min(d[a][b], c);}floyd();while (k--){int l, r;cin >> l >> r;if (d[l][r] > INF / 2) cout << "impossible" << endl;else cout << d[l][r] << endl;}return 0;
}
相关文章:
基础算法——搜索与图论
搜索与图论 图的存储方式2、最短路问题2.1、Dijkstra算法(朴素版)2.2、Dijkstra算法(堆优化版)2.3、Bellman-Ford算法2.4、SPFA求最短路2.5、SPFA判负环2.6、Floyd算法 图的存储方式 2、最短路问题 最短路问题可以分为单源最短路…...
redis优化编码之字符串
redis 优化编码之字符串 ### 字符串优化 字符串对象是redis内部最常用的数据类型。 所有的键是字符串对象值对象除了整数之外都是使用字符串存储lpush cache:type "redis" "tair" "memcache" "leveldb"创建如上一个链表 需要创建一…...
Python特定版本的安装/卸载/环境配置,Spyder安装教程
目录 1.Python安装 1.1 Python下载 1.2 下载特定版本 1.3 安装Python 1.4 修改安装 1.5 环境配置 1.6 卸载Python 2.Spyder安装使用 2.1 Spyder下载 2.1.1 官网下载Spyder 2.2.2 Github下载Spyder 2.2 安装 参考资料:网盘 1.Python安装 1.1 Python下载…...
全局搜索正则表达式(grep)
一.grep简介 grep 全程Globally search a Regular Expression and Print,是一种强大的文本搜索工具,它能使用特定模式匹配(包括正则表达式)搜索文本,并默认输出匹配行。Unix的grep家族包括grep和egrep 二.grep的工作…...
linux-12 关于shell(十一)ls
登录系统输入用户名和密码以后,会显示给我们一个命令提示符,就意味着我们在这里就可以输入命令了,给一个命令,这个命令必须要可执行,那问题是我的命令怎么去使用,命令格式有印象吗?在命令提示符…...
编写指针函数使向右循环移动m个位置
题目描述:有n个整数,要求你编写一个函数使其向右循环移动m个位置 请仔细阅读右侧代码,结合相关知识,在Begin-End区域内进行代码补充。 输入 输入n m表示有n个整数,移动m位 输出 输出移动后的数组 样例输入: 10 5 1 2 3…...
xvisor调试记录
Xvisor是一种开源hypervisor,旨在提供完整、轻量、移植且灵活的虚拟化解决方案,属于type-1类型的虚拟机,可以直接在裸机上启动。 启动xvisor步骤: 1、搭建riscv编译环境 首先从github上下载riscv-gnu-toolchain很费劲,建议直接从国内的源下载 git clone https://gitee…...
MongoDB-ObjectID 生成器
前言 MongoDB中一个非常关键的概念就是 ObjectID,它是 MongoDB 中每个文档的默认唯一标识符。了解 ObjectID 的生成机制不仅有助于开发人员优化数据库性能,还能帮助更好地理解 MongoDB 的设计理念。 什么是 MongoDB ObjectID? 在 MongoDB …...
CUDA 计时功能,记录GPU程序/函数耗时,cudaEventCreate,cudaEventRecord,cudaEventElapsedTime
为了测试GPU函数的耗时,可以使用 CUDA 提供的计时功能:cudaEventCreate, cudaEventRecord, 和 cudaEventElapsedTime。这些函数可以帮助你测量某个 CUDA 操作(如设置设备)所花费的时间。 一、记录耗时案例 以下是一个示例程序&a…...
PDF 文件如何转为 CAD 图纸?PDF2CAD 使用教程
在工程设计和建筑行业中,PDF 文件常常被用来分享和存档图纸。然而,当需要对这些图纸进行编辑或进一步开发时,静态的 PDF 格式就显得力不从心了。这时候,将 PDF 文件转换为可编辑的 CAD(计算机辅助设计)格式…...
【YashanDB知识库】php查询超过256长度字符串,数据被截断的问题
本文内容来自YashanDB官网,原文内容请见:https://www.yashandb.com/newsinfo/7488290.html?templateId1718516 问题现象 如下图,php使用odbc数据源,查询表数据,mysql可以显示出来,yashan显示数据被截断。…...
暴雨AI加速计算服务器新品X8840上市
用户输入简短的文字,大模型可以自动生成创意文本或图像;金融机构的风险评估和预测,大模型通过对金融数据的分析,可以识别异常交易行为;15秒内完成中英文作文的批改和评分,并提供针对性的改进建议࿰…...
在多个分布式机器间设置和使用 NFS(Network File System)共享目录的步骤如下:
在多个分布式机器间设置和使用 NFS(Network File System)共享目录的步骤如下: 1. 准备工作 确保所有参与的机器都在同一个网络中,并安装了 NFS 软件包。 在 Linux 系统上: sudo apt update && sudo apt install nfs-kernel-server -y # Ubuntu/Debian sudo yu…...
机器学习中的 Transformer 简介(第 1 部分)
目录 一、说明 二、为什么是 Transformer? 三、什么是 Transformer? 3.1 译者的类比 四、编码器部分 4.1 、从文本输入到输入嵌入 4.2 词嵌入 4.2 N倍编码器段 4.4 多头注意力机制 4.5 添加残差和层归一化 4.6 添加残差和层归一化 五、总结 一、说明 西如…...
D3实现站点路线图demo分享
分享一下通过D3实现的站点路线分布图,这是一个demo。效果图如下: 源码如下: <template><div class"map-test" ref"d3Chart"><div class"tooltip" id"popup-element"><span>…...
非文件形式的内存动态函数库调用接口
使用memfd的系统调用接口将动态库加载到proc虚拟文件系统,提供的fd为进程持有的句柄,通过dlopen的path指向此句柄,即可实现非文件系统加载动态链接库。 文章目录 一、memfd_create二、dl_open三、示例参考 一、memfd_create 接口名称int mem…...
liunx docker 部署 nacos seata sentinel
部署nacos 1.按要求创建好数据库 2.创建docker 容器 docker run -d --name nacos-server -p 8848:8848 -p 9848:9848 -p 9849:9849 -e MODEstandalone -e SPRING_DATASOURCE_PLATFORMmysql -e MYSQL_SERVICE_HOST172.17.251.166 -e MYSQL_SERVICE_DB_NAMEry-config -e MYSQL…...
解决没法docker pull问题
没想到国内源死差不多了,以下内容需要提前科学上网 su cd /etc/systemd/system/docker.service.d vim proxy.conf 参照下图修改,代理服务器改成你自己的。 [Service] Environment"HTTP_PROXYsocks5://192.168.176.180:10810" Environment&…...
面试小札:闪电五连鞭_2
1 请简单描述一下Java中的多线程。 多线程是指在一个程序中可以同时运行多个线程来执行不同的任务。在Java中,通过 java.lang.Thread 类来创建和控制线程。可以通过继承 Thread 类或者实现 Runnable 接口的方式来定义线程的执行逻辑。 线程有多种状态,…...
Milvus向量数据库06-RAG检索增强
Milvus向量数据库06-RAG检索增强 文章目录 Milvus向量数据库06-RAG检索增强1-学习目标2-参考网址3-执行过程记录1-到底什么是RAGRAG 的基本流程:为什么 RAG 优于传统的基于检索的方法:示例流程: 2-RAG和Elasticsearch对比3-RAG和向量数据库之…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
倒装芯片凸点成型工艺
UBM(Under Bump Metallization)与Bump(焊球)形成工艺流程。我们可以将整张流程图分为三大阶段来理解: 🔧 一、UBM(Under Bump Metallization)工艺流程(黄色区域ÿ…...
Vue3 PC端 UI组件库我更推荐Naive UI
一、Vue3生态现状与UI库选择的重要性 随着Vue3的稳定发布和Composition API的广泛采用,前端开发者面临着UI组件库的重新选择。一个好的UI库不仅能提升开发效率,还能确保项目的长期可维护性。本文将对比三大主流Vue3 UI库(Naive UI、Element …...
命令行关闭Windows防火墙
命令行关闭Windows防火墙 引言一、防火墙:被低估的"智能安检员"二、优先尝试!90%问题无需关闭防火墙方案1:程序白名单(解决软件误拦截)方案2:开放特定端口(解决网游/开发端口不通)三、命令行极速关闭方案方法一:PowerShell(推荐Win10/11)方法二:CMD命令…...
