题目描述
=
算法1
堆优化版 Dijkstra
时间复杂度
O(mlog n)
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
// 100010 通过不了测试
const int N = 150010;
// 堆里面存的是一个pair
typedef pair<int, int> PII;
// 稀疏图,用 邻接表 存
// 有重边 也没事,这个算法会保证我们选的是最短路径
int n, m;
// w[N] 存权重
int h[N], e[N], ne[N], w[N];
int dist[N];
// 为 true 说明这个点的最短路径已经确定
bool st[N];
int idx;
void add(int a, int b, int c)
{
// 有重边也不要紧,
// 假设1->2有权重为2和3的边,
// 再遍历到点1的时候2号点的距离会更新两次放入堆中
// 这样堆中会有很多冗余的点,
// 但是在弹出的时候还是会弹出最小值2+x(x为之前确定的最短路径),
// 并标记st为true,所以下一次弹出3+x会continue不会向下执行。
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 这里heap中为什么要存pair呢,首先小根堆是根据距离来排的,
// 所以有一个变量要是距离,
// 其次在从堆中拿出来的时候要知道知道这个点是哪个点,
// 不然怎么更新邻接点呢?所以第二个变量要存点。
priority_queue<PII, vector<PII>, greater<PII>> heap;
// 这个顺序不能倒,pair排序时是先根据first,再根据second,
// 这里显然要根据距离排序
heap.push({0, 1});
// 队列里面最多只有 m 个元素
while(heap.size())
{
// 取不在集合S中距离最短的点
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])
{
// i只是个下标,e中在存的是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];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m --)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int t = dijkstra();
cout << t << endl;
return 0;
}