需要前置知识朴素dijkstra
朴素dijk的算法中有一个瓶颈是选择出不在集合s中的离起点最近的点
在朴素的做法中,我们枚举整个d数组来找到这个点,其实可以考虑用小根堆优化
维护一个小根堆,其元素是一个结构体,成员有x,w两个,x代表点的编号,w代表d[x]
- 每次取出堆顶元素,如果已经在集合s中就抛去
- 如果不在集合s中,就加入之,然后尝试松弛
- 松弛成功的点y与松弛后的d[y]打包压入堆中
压堆操作的复杂度是log级别,所以堆优化dijk的时间复杂度是
O(NlogN)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, M = N;
int n, m;
int head[N], to[M], w[M], nxt[M], idx;
inline void add(int x, int y, int z)
{
to[++idx] = y;
w[idx] = z;
nxt[idx] = head[x];
head[x] = idx;
}
struct node{
int x, w;
node(int x, int w): x(x), w(w){}; //带参构造函数
friend bool operator > (const node &A, const node &B)
{
// 小根堆<greater>需要重载大于号
return A.w > B.w;
}
};
int d[N];
bool v[N];
void dijk(int s)
{
memset(d, 0x3f, sizeof d);
d[s] = 0;
// 小根堆的定义
priority_queue<node, vector<node>, greater<node> > Q;
Q.push(node(s, 0));
while (Q.size()) // 因为堆里可能存在s集合中的点,遇到要跳过,所以实际循环次数不确定
{
int x = Q.top().x;
Q.pop(); // 注意,堆中的w只有排序的作用,不需要取出直接pop掉
if (v[x]) // 遇到s中的点就跳过
continue;
v[x] = true; // 加入集合s
for (int i = head[x]; i; i = nxt[i])
{
int y = to[i];
if (d[y] > d[x] + w[i])
{
d[y] = d[x] + w[i];
Q.push(node(y, d[y]));
}
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
}
dijk(1);
cout << (d[n] == d[0] ? -1 : d[n]) << endl;
return 0;
}