dijkstra算法的核心在于每次从未被确定的顶点中选出目前最短距离最小的顶点。 朴素版dijkstra算法的问题在于, 它对所有的顶点都执行搜索, 并且每次搜索完全无关, 时间复杂度恒定在O(n).
但其实我们搜索的范围只需要是最短距离被更新过的即可。基于这样一个事实, 可以用最小堆来优化搜索过程。
在每次取出最小距离的顶点后, 我们照常更新它的邻接点的最短距离, 并把更新过最短距离的邻接点加入堆中。
由于一个顶点可能被多个不同顶点加入堆中, 以此我们取出顶点后要判断其最短路径是否已被确定。
在实现形式上, 用stl中的priority_queue作为最小堆, 由于我们每次要取出的是顶点的编号, 而作为排序的值是它们当前的最短路径值, 所以用一个pair作为堆中的元素, 最短路径值作为pair的first, 因为pq排序pair先考虑first, 其次考虑second
priority_queue<pii, vector<pii>, greater<>> heap;
//
// Created by trudbot on 2022/7/8.
//
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define Inf 0x3f3f3f3f
using namespace std;
const int N = 1e6+10;
int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N];
bool vis[N];
void add(int x, int y, int z)
{
e[idx] = y, w[idx] = z, ne[idx] = h[x], h[x] = idx++;
}
void dijkstra(int bg)
{
priority_queue<pii, vector<pii>, greater<>> heap;
memset(dist, 0x3f, sizeof dist);
dist[bg] = 0;
heap.push({0, bg});
int cv;
while(!heap.empty())
{
cv = heap.top().second;
heap.pop();
if(vis[cv]) continue;
for(int i=h[cv]; i!=-1; i=ne[i])
{
int dest = e[i];
if(dist[dest] > dist[cv] + w[i])
{
dist[dest] = dist[cv] + w[i];
heap.push({dist[dest], dest});
}
}
vis[cv] = true;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
memset(h, -1, sizeof h);
int x, y, z;
while(m--)
{
cin >> x >> y >> z;
add(x, y, z);
}
dijkstra(1);
cout << (dist[n] == Inf ? -1 : dist[n]);
return 0;
}