第三讲 搜索与图论¶
一定要多写！每个算法写个五六遍基本就会了
深度优先遍历 DFS¶
dfs和bfs搜索的结构都像一棵树一样，搜索的顺序不一样
dfs尽可能往深了搜，碰到叶节点回溯
dfs执着，一条路必定会走到头
从数据结构来看，DFS使用stack，使用空间O(h)，空间上有绝对优势，但不具有“最短路”的性质
算法思路比较奇怪的或对空间要求高的一般是DFS
两个重要概念：回溯和剪枝
如果觉得难以思考，就从搜索树的角度来考虑
dfs其实就是递归，没有必要去别的太开
dfs的搜索框架很多需要从题目进行分析
dfs俗称暴力搜索，最重要的是遍历所有方案的顺序
842. 排列数字¶
看着是一棵树的形式，但是存的时候只会存当前的路径，所以不需要将整个树存储下来，系统会有一个隐藏的栈来帮我们搞定，不需要我们开额外的空间
回溯里面非常重要的一点就是要恢复现场，用完的东西一定要放回去
#include <iostream>
using namespace std;
const int N = 10;
int n;
int path[N];
bool st[N]; // bool默认0，false
void dfs (int u) {
if (u == n) {
for (int i = 0; i < n; i ++) printf("%d ", path[i]);
puts("");
return;
}
for (int i = 1; i <= n; i++) {
if (!st[i]) {
path[u] = i;
st[i] = true;
dfs(u + 1);
// 恢复现场
path[u] = 0; //这一步实际上可以不写，因为后面每次用的时候path[u]都被重新赋值了
st[i] = false;
}
}
}
int main () {
cin >> n;
dfs(0);
return 0;
}
843. n-皇后问题¶
思考一：
- 完全按照全排列的思路，枚举每一行的皇后应该放在哪一列上去
也可以边做便判断
剪枝就是判断当前这个选择一定是不合法的
思考二：朴素的思考方式对于每个格子来说，有放皇后和不放皇后的两种情况，对两种情况分别进行dfs即可
diagonal 对角线
思考对角线的时候，思考y = x + b或者y = -x + b
对于一条线上的点来说他们的截距应该相等
即 b = y - x 或者b = y + x
因为我们定义的dg[N] 和udg[N]都是0~N，所以对可能变成负数的y - x + N/2即可
dfs是思路，没有模板，重要的是顺序
1. 全排列的思路，对每行进行讨论¶
#include <iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u) {
if (u == n) {
for (int i = 0; i < n; i++) puts(g[i]);
puts("");
return;
}
for (int i = 0; i < n; i++) {
if(!col[i] && !dg[u + i] && !udg[n - u + i]) {
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[n - u + i] = true;
dfs(u + 1);
col[i] = dg[u + i] = udg[n - u + i] = false;
g[u][i] = '.';
}
}
}
int main () {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g[i][j] = '.';
}
}
dfs(0);
return 0;
}
2. 对每个点都进行放和不放的讨论¶
时间效率差
#include <iostream>
using namespace std;
const int N = 20;
int n;
char g[N][N];
int row[N], col[N], dg[N], udg[N];
void dfs(int x, int y, int s) {
if (y == n) y = 0, x++;
if (x == n) {
if (s == n) {
for (int i = 0; i < n; i++) {
puts(g[i]);
}
puts("");
}
// 无论什么情况都要return的注意
return;
}
// 第一种情况是直接不放皇后
dfs(x, y + 1, s);
// 第二种情况是在符合情况的条件下放皇后
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
g[x][y] = 'Q';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
// 注意s + 1
dfs(x, y + 1, s + 1);
// 回溯
g[x][y] = '.';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
}
}
int main () {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j ++) {
g[i][j] = '.';
}
}
dfs(0, 0, 0);
return 0;
}
宽度优先遍历 BFS¶
眼观六路耳听八方，搜索的时候使一层一层的搜
BFS使用queue，使用空间O(2^h)，第一次扩展到的点，必定具有“最短路”的性质（需要每个边的权重都是1）
涉及到最小步数、最短距离、最少操作几次，基本上都是BFS
dp问题是一种特殊的最短路问题，没有环存在的最短路问题
bfs一般是有一个常用的框架的！
框架：
将初始状态放到队列里面 queue
当队列不空 while(queue){
每一次把队头拿出来，扩展队头
}
844.走迷宫¶
为什么需要队列来维护：那些走不通的点，在下一层遍历的时候就不需要任何考虑了
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n, m;
int g[N][N];//存放地图
int d[N][N];//存 每一个点到起点的距离
PII q[N * N];//手写队列
int bfs() {
int hh = 0, tt = 0;
q[0] = {0, 0};
memset(d, -1, sizeof d);//距离初始化为- 1表示没有走过
d[0][0] = 0;//表示起点走过了
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while (hh <= tt) {
auto t = q[hh++]; // 每一次取出队头，尝试往上下左右
for (int i = 0; i < 4 ; i++) { // 四个方向
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
d[x][y] = d[t.first][t.second] + 1;
q[++tt] = {x, y}; // 新的队头
}
}
}
return d[n - 1] [m - 1];
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i ++ )
for(int j = 0; j < m; j ++ )
cin >> g[i][j];
cout << bfs() << endl;
return 0;
}
如何去存储路径¶
只要记录一下每个点是从哪个点扩散出来的就行
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n, m;
int g[N][N];//存放地图
int d[N][N];//存 每一个点到起点的距离
PII q[N * N], Prev[N][N];
int bfs() {
int hh = 0, tt = 0;
q[0] = {0, 0};
memset(d, -1, sizeof d);//距离初始化为- 1表示没有走过
d[0][0] = 0;//表示起点走过了
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while (hh <= tt) {
auto t = q[hh++]; // 每一次取出队头，尝试往上下左右，每一次都只会扩散一个数的外面一格，然后就是下一个数的外面一格，所以不用担心某一个数直接扩散去终点了
for (int i = 0; i < 4 ; i++) { // 四个方向
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1) {
d[x][y] = d[t.first][t.second] + 1;
Prev[x][y] = t;
q[++tt] = {x, y}; // 新的队尾
}
}
}
int x = n - 1, y = m - 1;
while (x || y) {
cout << x << ' ' << y << endl;
auto t = Prev[x][y];
x = t.first, y = t.second;
}
return d[n - 1] [m - 1];
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i ++ )
for(int j = 0; j < m; j ++ )
cin >> g[i][j];
cout << bfs() << endl;
return 0;
}
树与图的存储¶
树与图的存储
树是一种特殊的图，与图的存储方式相同。树是无环连通图。
图分成有向图和无向图，无向图是一种特殊的有向图
对于无向图中的边ab，存储两条有向边a->b, b->a。 因此我们可以只考虑有向图的存储。
(1) 邻接矩阵：g[a][b][a, b] 存储边a->b，用重复边的话只能保留一条相同的边
(2) 邻接表：用的比较多
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
// h[N]存的是n个链表的链表头，e存的是每个节点的值，ne是每个节点的next指针
// 图中的每个点都是链表头
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a ] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);
树与图的深度优先遍历¶
深度优先遍历和宽度优先遍历每个点只会遍历一次
bool数组用来存哪些点已经被遍历过了
时间复杂度 O(n+m)，n 表示点数，m表示边数
(1) 深度优先遍历 —— 模板题 AcWing 846. 树的重心
删除中心 = 将一棵树尽可能碎地拆开来
对于每个点都求出最大值，然后求所有最大值地最小值
如何求每个点删掉之后地最大值，深度优先遍历按的特点：算出每个子树的大小
int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010, M = N * 2;
int n, m;
int h[N], e[M], ne[M], idx;
bool st[N];
int ans = N;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// 返回以u为根的子树的大小
int dfs (int u) {
st[u] = true; // 标记一下，已经被搜过了
int sum = 1, res=0;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]){
int s = dfs(j);
res = max(res, s);
sum += s;
}
}
res = max(res, n -sum); // 除去所有单向发出去的，其他应该连成一个连通块了
ans = min(ans, res);
return sum;
}
int main () {
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1);
cout << ans << endl;
return 0;
}
树与图的宽度优先遍历¶
(2) 宽度优先遍历 —— 模板题 AcWing 847. 图中点的层次
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 表示点j已经被遍历过
q.push(j);
}
}
}
847. 图中点的层次¶
宽搜中第一次中找到这个点的时候就是最短路径
注意原来的h[N]指向的是-1就是空，这里的void add(int a, int b)和单链表的存储一模一样
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N], q[N]; // d是距离，q是队列
void add (int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs() {
int hh = 0, tt = 0;
q[0] = 1;
memset(d, -1, sizeof d);
d[1] = 0;
while(hh <= tt) {
int t = q[hh++];
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] == -1) {
d[j] = d[t] + 1;
q[++tt] = j;
}
}
}
return d[n];
}
int main () {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs() << endl;
return 0;
}
拓扑排序¶
时间复杂度 O(n+m)，n表示点数，m 表示边数
有向图才有拓扑序列
图的拓扑序列：针对有向图，若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x在 A 中都出现在 y之前，则称 A是该图的一个拓扑序列。
123这个序列，需要比较12，13，23，需要都是前面那个数指向后面那个数
有环不可能有拓扑序
有向无环图一定存在一个拓扑序列，所以有向无环图也被称为拓扑图
有向图每个点都有两个度数：入度和出度
入度指一个点被几个点指
出度指指向几个点
所以拓扑图中，所有入度为0的点都可以作为起点（因为不会有任何一个点在我前面）
然后对每个点进行bfs
一个有向无环图，一定至少存在一个入度为0的点
bool topsort()
{
int hh = 0, tt = -1;
// d[i] 存储点i的入度
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (-- d[j] == 0)
q[ ++ tt] = j;
}
}
// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
return tt == n - 1;
}
848.有向图的拓扑序列¶
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N]; //q存的是队列，d存的是入度
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool topsort() {
int hh = 0, tt = -1;
for (int i =1; i <= n; i++) {
if (!d[i]) { // 把所有入度为0的点插到队列里面去
q[++tt] = i;
}
}
while(hh <= tt) {
int t = q[hh++]; // 出队的顺序是拓扑序即q里面的顺序
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
d[j] --; // 减入度
if (d[j] == 0) q[++tt] = j;
}
}
return tt == n -1; // 说明一共进了n个点，所有点都进入队列了
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
add(a, b);
d[b] ++;// 不要忘记更新入度
}
if (topsort()){
for(int i = 0; i < n; i++) printf("%d ", q[i]);
}
else puts("-1");
return 0;
}
最短路算法¶
最短路算法不会让你证明它算法的正确性，考察的是如何将题目转化为最短路问题，侧重于实践，不侧重于原理
有向图和无向图的最短路算法没有区别，最短路问题里面只用去考虑有向图就行了，无向图是一种特殊的有向图
常见的最短路算法分为两大类：
单源最短路问题¶
从1号点到n号点的最短路，从1号点从其他所有点的最短路
1. 所有边的权重都是正值¶
- 使用朴素Dijkstra算法 O(n^2 + m) (约定n表示点数，m表示边数)
- 堆优化的Dijkstra算法 O(mlogn)
可以发现朴素的做法的时间复杂度和边数无关，所以当点非常多的稠密图时，我们可以使用朴素算法
反之，稀疏图时，m和n时一个级别的，n^2非常大
2. 存在负权边¶
- Bellman-Ford 算法 O(nm)
- SPFA算法对上面的算法进行了优化，一般是O(m)复杂度，最化是O(nm)，效率一般比上面那个高
并不是所有题目都可以用SPFA算法可以做，如果限制经过的边数<k，就不能用SPFA
多源汇最短路问题¶
源点--起点 汇点-- 终点
任选一个起点或者终点，求他们的最短路
Floyd 算法 时间复杂度O(n^3)¶
朴素dijkstra算法¶
Dijkstra算法是一种用于解决单源最短路径问题的图算法。它由荷兰计算机科学家Edsger Dijkstra于1956年提出。
该算法通过从起始节点开始，逐步选择距离起始节点最近的节点，并更新其他节点的最短路径距离，直到找到到达目标节点的最短路径或者遍历完所有节点。
Dijkstra算法的基本思想是维护一个距离表，记录从起始节点到其他节点的当前最短距离。在每一次迭代中，选择距离起始节点最近的未访问节点作为当前节点，并通过计算从当前节点到其邻居节点的距离，更新邻居节点的最短路径距离。重复此过程直到到达目标节点或者所有节点都被访问。
Dijkstra算法的关键操作是在每次迭代中选择距离起始节点最近的节点，以及更新邻居节点的最短路径距离。为了实现这些操作，通常使用优先队列（例如最小堆）来存储待访问节点和对应的距离。
Dijkstra算法适用于没有负权边的加权有向图或无向图。它可以用于求解从一个节点到其他所有节点的最短路径，或者仅计算从一个节点到指定目标节点的最短路径。
尽管Dijkstra算法在时间复杂度上较高（O(V^2)，其中V是节点数），但它在实践中通常表现良好，并且被广泛应用于路由计算、地理信息系统和网络优化等领域。
模板：
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1; // 在还未确定最短路的点中，寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
基于贪心的思路
基本算法思路：求的是1号点到其他所有点的最短路距离
- 先初始化我们的举例，dist[1] = 0, dist[i] = 正无穷
- for (i : 0 ~ n ) 迭代过程，每一次确定一个最短路
找到当前已经确定最短距离的点存到S
t不在s中举例最近的点
把t加到s中去
用t更新其他点的距离
从t出去的所有边能不能更新其他点的距离
dist[x] > dist[tx] 更新
简而言之，就是每次更新挑最短路的那个来更新其他剩下点的距离
稠密图邻接矩阵来存
稀疏图用邻接表来存
Leetcode里面图论的题目非常少，笔试全是图论和dp
如果所有边是正的，两点之间只要存储最短的一条边就行
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510;
int g[N][N]; //为稠密阵所以用邻接矩阵存储
int dist[N]; //用于记录当前状态下每一个点距离第一个点的距离
bool st[N]; //用于记录该点的最短距离是否已经确定
int n,m;
int Dijkstra()
{
memset(dist, 0x3f,sizeof dist); //初始化距离 0x3f代表无限大
dist[1]=0; //第一个点到自身的距离为0
for(int i=0;i<n;i++) //有n个点所以要进行n次 迭代
{
int t=-1; //t存储当前访问的点
for(int j=1;j<=n;j++) //这里的j代表的是从1号点开始
if(!st[j]&&(t==-1||dist[t]>dist[j])) // 为了存储所有点中的最小值，在所有false的点中找dist最小的一个点
t=j;
st[t]=true;
for(int j=1;j<=n;j++) //依次更新每个点所到相邻的点路径值
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
if(dist[n]==0x3f3f3f3f) return -1; //如果第n个点路径为无穷大即不存在最低路径
return dist[n];
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g); //初始化图 因为是求最短路径
//所以每个点初始为无限大
while(m--)
{
int x,y,z;
cin>>x>>y>>z;
g[x][y]=min(g[x][y],z); //如果发生重边的情况则保留最短的一条边
}
cout<<Dijkstra()<<endl;
return 0;
}
工程化的代码和算法代码不一样
工程化追求的是让别人看懂，日后好修改好维护
堆优化版dijkstra¶
m和n^2是一个级别的时候就是稠密图
用堆来做，每次都能找到距离最近的点
堆两种实现方式：
- 手写堆 可以维护n个数
- 用优先队列来维护，不支持修改任意一个元素，实现方式是冗余，每次都是向里面插入数，堆里的元素就可能回变成m个，时间复杂度和手写堆是一个数量级
不用手写堆
优先队列里面有很多冗余
模板：
typedef pair<int, int> PII;
int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first存储距离，second存储节点编号
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
850.Dijkstra求最短路2¶
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;// w表示权重
int dist[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(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap; // 这个就是小根堆的定义方式，不用纠结为什么要这么写，背过就行了vector表示堆由什么来实现，greater是另外一个参数
heap.push({0, 1});
while (heap.size())
{
auto t = heap.top(); // 每次找到当前距离最近的点
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
printf("%d\n", dijkstra());
return 0;
}
另一种做法和注释
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010; // 把N改为150010就能ac
// 稀疏图用邻接表来存
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dist[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定
int n, m;
void add(int x, int y, int c)
{
// 有重边也不要紧，假设1->2有权重为2和3的边，再遍历到点1的时候2号点的距离会更新两次放入堆中
// 这样堆中会有很多冗余的点，但是在弹出的时候还是会弹出最小值2+x（x为之前确定的最短路径），
// 并标记st为true，所以下一次弹出3+x会continue不会向下执行。
w[idx] = c;
e[idx] = y;
ne[idx] = h[x];
h[x] = idx++;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆
// 这里heap中为什么要存pair呢，首先小根堆是根据距离来排的，所以有一个变量要是距离，
// 其次在从堆中拿出来的时候要知道知道这个点是哪个点，不然怎么更新邻接点呢？所以第二个变量要存点。
heap.push({ 0, 1 }); // 这个顺序不能倒，pair排序时是先根据first，再根据second，
// 这里显然要根据距离排序
while(heap.size())
{
PII k = heap.top(); // 取不在集合S中距离最短的点
heap.pop();
int ver = k.second, distance = k.first;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i]; // i只是个下标，e中在存的是i这个下标对应的点。
if(dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({ dist[j], j });
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
while (m--)
{
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
add(x, y, c);
}
cout << dijkstra() << endl;
return 0;
}
Bellman-Ford算法¶
Bellman-Ford算法是一种用于解决单源最短路径问题的图算法。它由美国数学家Richard Bellman和Leslie Ford在1958年提出。
该算法适用于带有负权边的加权有向图或无向图，包括检测负环的情况。与Dijkstra算法不同，Bellman-Ford算法可以处理包含负权边的图，并且能够检测到负权环。然而，由于需要对所有边进行松弛操作的迭代，Bellman-Ford算法的时间复杂度比Dijkstra算法高。
Bellman-Ford算法的基本思想是通过对每条边进行松弛操作来逐步更新节点的最短路径距离。算法从起始节点开始，将起始节点的最短路径距离初始化为0，将其他节点的最短路径距离初始化为正无穷大。然后，在每一轮迭代中，遍历图中的所有边，并尝试通过当前边进行松弛操作以更新节点的最短路径距离。重复执行这个过程，直到没有更多的边可以使得路径距离变短为止。
Bellman-Ford算法还包含一个额外的步骤，即检测负权环。在每次迭代之后，再进行一轮遍历，并检查是否存在可以进一步缩短路径距离的边。如果在最后一轮迭代中仍然可以更新节点的最短路径距离，则说明图中存在负权环。
尽管Bellman-Ford算法的时间复杂度为O(V * E)，其中V是节点数，E是边数，相对于Dijkstra算法的O(V2)和Floyd-Warshall算法的O(V3)，Bellman-Ford算法在处理带有负权边的图时是一种有效的选择。
然而，需要注意的是，Bellman-Ford算法在图中存在负权环的情况下并不会给出正确的最短路径距离，因为负权环可以使路径距离无限减小。因此，在使用Bellman-Ford算法时，通常需要进行额外的判断来检测负权环的存在。
时间复杂度 O(nm)，n示点数，m表示边数 注意在模板题中需要对下面的模板稍作修改，加上备份数组，详情见模板题。
基于动态规划
迭代n次 for n 次
for 所有边a,b,w 存在一条a到b的边，权重是w
int n, m; // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}