当求单源最短路，且边权为正值时，使用Dijkstra算法求解最短路问题
Dijkstra分为朴素版和堆优化版：
朴素版用于稠密图的求解最短路：不妨令顶点数为n，边数为m；顶点数和边数的关系式为：m <= n * (n - 1) / 2；估算为：m的最大值为n^2。当题目给出的数据范围形式是n 和 m 分别给出，并且m的最大值约为n^2，这个时候表示给出的图为稠密图，使用邻接矩阵存储边权。
堆优化版用于稀疏图的求解最短路：n 和 m 的关系还是如上；当题目给出的数据范围 n 和 m 是相同的，那么使用邻接表，在加上一个数组存储边权即可。
朴素版Dijkstra算法主要是三步：（时间复杂度分析：设点数为 n， 边数为 m。）
- 寻找 n - 1次最短路 （ O(n))
- 找到没有确定最短路的点中的最短路 (O( n^2 ))
- 用这个找到的最短路的终点，去更新其他点的距离 (O( m ))
可以发现整个算法中最糟糕的是第二步，O(n^2)。那么我们可以使用小根堆优化，使第二步时间复杂度到O(n)。但是第三步需要改变，在堆中并不能修改某个点，只能push，所以每次的时间复杂度为O(log n)。整体下来是O(m log n)。当是稠密图时，m = n^2，并没有起到优化作用，但是当m和n的范围一样，那么就可以起到优化作用了，所以在稀疏图时使用堆优化的Dijkstra。
朴素版
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, M = 1e5 + 10;
int n, m;
int g[N][N]; // 邻接矩阵，表示 i 和 j 之间的边权为 g[i][j]
int dist[N]; // 最短距离
bool st[N]; // 对于每一个顶点是否确定好了最短路int dijkstra1()
{memset(dist, 0x3f, sizeof dist); // 并不直达就设为INFdist[1] = 0;for(int i = 0; i < n - 1; i++) // 有 n 个 顶点，只需要循环 n - 1次{int t = -1;for(int j = 1; j <= n; j++) // 找到没有确定以1为起点的最短路 的点中 最短的边if(!st[j] && (t == -1 || dist[t] > dist[j])) // 是否确定看st数组t = j;if(t == n) break; // 假如已经到了终点就跳出循环st[t] = true;for(int j = 1; j <= n; j++) // 根据每次找到的最短边的终点 t, 更新1 ~ t ~ j 的最短路径dist[j] = min(dist[j], dist[t] + g[t][j]);}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];}int main()
{scanf("%d%d", &n, &m);memset(g, 0x3f, sizeof g); // 初始设各点不可直达，设为INFwhile(m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);if(a == b) continue; // 去掉环g[a][b] = min(g[a][b], c); // 去掉重边}printf("%d", dijkstra1());return 0;
}堆优化版
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1e6 + 10;
typedef pair<int, int> PII;
int h[N], w[N], e[N], ne[N], idx; // w数组表示边权
int dist[N];
bool st[N];
int n, m;
void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}int dijkstra2()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap; // 小根堆heap.push({0, 1});while(!heap.empty()){PII t = heap.top();heap.pop();int distance = t.first, ver = t.second;if(st[ver]) continue; // 以及确定过了，丢弃st[ver] = true;for(int i = h[ver]; ~i; i = ne[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()
{memset(h, -1, sizeof h);scanf("%d%d", &n, &m);while(m--){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c); // 堆优化版中不需要考虑重边和环}printf("%d", dijkstra2());return 0;
}
