DAY 4
1.AcWing 850. Dijkstra求最短路 ii
考察点:堆优化Dijkstra,求最短路问题 适合于稀疏图,利用邻接表来存储
邻接表不需要对重边做特殊的处理
(1)基础知识
时间复杂度分析:
堆优化Dijkstra
堆优化版Dijkstra与朴素版的区别主要就是在用寻找最小距离t时采用堆的方式来实现。堆其实看做是一种完全二叉树的数组对象,是最高效的优先级队列,分为小根堆和大根堆。
堆的实现方式:
手写堆 | 优先队列 |
n个数,方便插入和修改一个数 | 不支持修改任意一个数,实现方式是冗余 m个数,但是两种方式的时间复杂度相同 |
优先队列:(可以解决一些贪心问题,以及Dijkstra的优化问题)
1. priority_queue(优先队列),底层是用堆的数据结构来实现,队首元素为队列中优先级最高的一个,在插入数据时,采用冗余的实现方式,优先队列底层的数据结构堆(heap)会随时调整结构。
2. 使用时需要添加#include<queue>,using namespace std;
其定义写法为priority_queue<typename>name;
3. 优先队列只能通过top()函数来访问队首元素,优先级最高(堆顶元素),没有front(),back()函数,具有push(),top(),empty().q.size();
4. 队列内优先级设置:priority_queue<int,vector<int>,less<int>>q
队首是优先级最高的,参数2 vector<int>是承载底层数据结构堆的容器,可以根据类型修改vector的数据类型,参数3是对第一个参数的比较类,less<int>表示数字大的优先级越大(大根堆),great<int>表示数字小的优先级越大(小根堆)
最终题解代码
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int,int>PII;//第一个参数存储距离起点的距离,第二个参数存储是第几个数
const int N = 1e6+10;
int n, m;
int h[N],e[N],ne[N],w[N],idx;//为稀疏图,所以采用邻接表来存储,w[N]为权重
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); //初始化距离 0x3f代表无限大
dist[1] = 0;//第一个点到自身的距离为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, distance = t.first;//以t为中转站,依次更新每个点所到相邻的点路径值
if (st[ver]) continue;
st[ver] = true;//遍历t
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; //如果第n个点路径为无穷大即不存在最低路径
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("%dn", Dijkstra());
return 0;
}
2..AcWing 853. 有边数限制的最短路
考察点:bellman-ford(权重存在负数)
(1)bellman-ford的存储f方式非常多,可以使用邻接表,也可以使用结构体来存储图
(2)Bellman - ford 算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在 n-1 次松弛后还能更新,则说明图中有负环,因此无法得出结果,否则就完成。
(通俗的来讲就是:假设 1 号点到 n 号点是可达的,每一个点同时向指向的方向出发,更新相邻的点的最短距离,通过循环 n-1 次操作,若图中不存在负环,则 1 号点一定会到达 n 号点,若图中存在负环,则在 n-1 次松弛后一定还会更新)
(3)bellman - ford算法的具体步骤
for n次
for 所有边 a,b,w (松弛操作)
dist[b] = min(dist[b],back[a] + w)
注意:back[] 数组是上一次迭代后 dist[] 数组的备份,由于是每个点同时向外出发,因此需要对 dist[] 数组进行备份,若不进行备份会因此发生串联效应,影响到下一个点
注:能求出来最短路的情况下是没有负权回路的(spfa),bellman-ford是可能的
(5) 时间复杂度:O(nm) 在题目中如果有对边数进行限制的时候,只能使用bellman-ford算法,其他情况下一般都可以被性能更好的算法替换。
需要注意在t对后续点进行更新的时候,需要备份,防止发生距离串联,影响边数限制。
(6)strcpy和memcpy主要有以下3方面的区别。
复制的内容不同。strcpy只能复制字符串,而memcpy可以复制任意内容,例如字符数组、整型、结构体、类等。
复制的方法不同。strcpy不需要指定长度,它遇到被复制字符的串结束符"