题目描述
鄙人才疏学浅 题解写下来也只是为了自己日后复习之用
当然也是因为y总在视频里稍微提了一下手写堆 所以我就很在意
不敢说是为了给大家展示完美的写法 如果大家觉得我哪里写的不够清楚 请尽管留言
dijkstra算法 用手写堆实现 即支持y总视频里所说的heap_swap的那种堆
如果用了这种手写堆 那么堆中最多只会有和节点数相同的元素数量 原因是因为可以及时对堆里的元素进行实时更新
而如果用了模板的优先队列 那么 队列中最多有边数那么多的元素数量
但是用了模板实现的方式只要加个continue 就会使得这两者的复杂度大致没有区别
但最重要的目的是 用手写堆去实现这个算法 能极大的加深你对手写堆的理解(虽然手写堆熟练之后似乎也没有什么用)
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool found[N];
//这里就是手写堆的基本的三个函数的代码
int heap[N], hp[N], ph[N], sizee;
void heap_swap(int a, int b)
{
swap(ph[hp[a]], ph[hp[b]]);
swap(hp[a], hp[b]);
swap(heap[a], heap[b]);
}
void down(int k)
{
int t = k;
if (k * 2 <= sizee && heap[t] > heap[k * 2]) t = k * 2;
if (k * 2 + 1 <= sizee && heap[t] > heap[k * 2 + 1]) t = k * 2 + 1;
if (k != t)
{
heap_swap(k, t);
down(t);
}
}
void up(int k)
{
while (k / 2 && heap[k] < heap[k / 2])
{
heap_swap(k, k / 2);
k >>= 1;
}
}
//下面是正文
//这里区分三个概念 节点的ID(即由idx形成的) (如果不理解说明数组实现单链表还没掌握)
节点(vertex) 即(题目样例中所给的每一行中前两个的那种数字)
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
sizee++;
ph[1] = sizee; //节点在堆中的下标
hp[sizee] = 1; //实现 用堆中的下标来识别这个是哪个vertex
heap[sizee] = 0;//存储距离 为了排序
up(sizee);
while (sizee)
{
int cur_dist = heap[1];
int cur_ver = hp[1];
heap_swap(1, sizee--);
down(1);
for (int i = h[cur_ver]; i != -1; i = ne[i])
{
int j = e[i]; //i是节点ID j是vertex
if (dist[j] > cur_dist + w[i])
{
dist[j] = cur_dist + w[i];
if (ph[j] != 0)//修改之前已经在堆中的j节点
//记住 对于堆来说,他对 用来实现邻接表的idx 这个东西是没有概念的
//即这是一种对底层i的抽象 类似在cpu看来根本没有RAM和cahce之分
{
heap[ph[j]] = dist[j];
up(ph[j]);
down(ph[j]);
}
else//全新节点
{
sizee++;
ph[j] = sizee;
hp[sizee] = j;
heap[sizee] = dist[j];
up(sizee);
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
}
cout << dijkstra();
}
感谢感谢,一直想找手写堆的写法
为啥手写堆要用heap-swap而不是swap呢?模拟堆的heap_swap只是为了删除第k个插入的元素时防止找不到,而这个djikstra不就是每次找最小的删后再找最小的删,貌似没有用到第k个插入的这个关系啊..
更新距离时用到了映射啊
焯,我悟了orz