**基本**和单源最短路是重题
因为题目中说了Dijkstra，干啥还用~~死了的SPFA?~~
估计用Floyd100%会挂...
那么就用堆优化的Dijkstra~~（迪杰克斯歘）~~
关于什么是Dijkstra?
但是我自己都觉得那个讲的太复杂，就简单的讲一下吧
Dijkstra不会死去的条件：
该有权图不含负权边时间复杂度为O(n^2)
介绍一下：
Dijkstra类似于贪心
首先先确定一个源点（这里就是1号点），先把所有Dis(1,i)（i!=1）都定为INF，然后先遍历一遍，把与点1相连的点（即只用走一个连边）的点i的距离都第一次直接处理为Dis(1,i)
第二次遍历把与`Dis(1,i)<INF`的点有连接的点j的Dis处理为Dis(1,i,j)意为用i点的Dis来给j点附上Dis，可以说`Dis(1,j)=Dis(1,i)+Dis(i,j)；`
之后我们重复第二次的操作，不过这次会多一种情况，即用Dis(j)来处理Dis(i)，就是说这次遍历到j点的时候，如果有`Dis(1,j,i)<Dis(1,i)<INF`,我们就Dis(1,i)的值变为 `min(Dis(1,j),Dis(1,j)+Dis(j,i))`
遍历过后，如果仍有Dis(k)=INF的话，就证明点1无法到点k，所以我们只需要输出`-1`就可以了
那么什么是堆优化Dijkstra呢？
每次扩展一个距离最小的点，再更新与其相邻的点的距离。
如何寻找距离最小的点？
优化方案是建一个小根堆，小根堆里存储由当前结点更新距离的所有点，那么堆顶就是距离最小的点
建一个小根堆，用来存储结点的序号，用一个数组来存储第i个结点在堆中的位置，用一个标记数组来记录结点是否在堆中
对于小根堆的操作还是基本的put() 和get() ，但由于有的结点已经在堆中了，所以可以把put() 拆为插入堆和调整位置两个部分
```
1.将与源点相邻的点进行松弛操作后加入堆
2.取出位于堆顶的结点
3.若取出的点为终点，则结束算法
4.将与当前结点相邻的点进行松弛操作
(1)如果该点已经在堆中，就调整在堆中的位置
(2)如果该点不在堆中，就加入堆
```
代码如下
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <queue> using namespace std; typedef long long ll; const int MAXN = 1e5 + 10; const ll INF = 1ll<<62; vector<int>e[MAXN]; vector<int>w[MAXN]; bool vis[MAXN]; ll d[MAXN]; int pre[MAXN]; int n; struct Node { ll d; int u; bool operator < (const Node & rhs) const { return d > rhs.d; } }; void Dijkstra() { priority_queue<Node>q; for( int i=1; i<=n; i++ ) d[i] = INF; d[1] = 0; memset(vis, 0, sizeof(vis)); Node tn; tn.d = 0, tn.u = 1; q.push(tn); while(!q.empty()) { Node t = q.top(); q.pop(); int u = t.u; if(vis[u]) continue; vis[u] = true; for( int i=0; i<e[u].size(); i++ ) { int v = e[u][i]; if(d[v] > d[u] + w[u][i]) { d[v] = d[u] + w[u][i]; pre[v] = u; tn.d = d[v], tn.u = v; q.push(tn); } } } } int main() { int m; while(scanf("%d%d", &n, &m) != EOF) { for( int i=1; i<=n; i++ ) e[i].clear(), w[i].clear(); int a, b, c; for( int i=0; i<m; i++ ) { scanf("%d%d%d", &a, &b, &c); e[a].push_back(b); w[a].push_back(c); e[b].push_back(a); w[b].push_back(c); } Dijkstra(); if(d[n] == INF) printf("-1\n"); else { e[1].clear(); e[1].push_back(n); while(pre[n] != 1) { n = pre[n]; e[1].push_back(n); } e[1].push_back(1); for( int i=e[1].size()-1; i>0; i-- ) printf("%d ", e[1][i]); printf("%d\n", e[1][0]); } } return 0; }
原文：https://www.cnblogs.com/j1yx/p/11066192.html