解决求节点间最短路径的问题。模板比较固定，请自行查找材料学习算法思想，按照模板多写几遍就会写了。

5.8.4.1 Dijkstra 算法

非负权图的单源最短路稳妥方法。

  1. // Dijkstra 使用堆优化，比较通用的版本
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 504;
  5. const int M = 1e5 + 4;
  6. typedef pair<int, int> P;   // pair<边权值, 终点>，默认按第一个元素排序，顺序不能颠倒！
  7. priority_queue<P, vector<P>, greater<P> > q;    // 堆，C++11前，两个右尖括号必须用空格隔开，否则编译为>>位右移运算
  8. vector<P> g[N];                // 邻接表
  9. P p;
  10. int dist[N];                // dist[i] 表示起点到 i 的距离
  11. bool vis[N];
  12. int n, m;
  13. // @s 为起点
  14. void dj(int s) {
  15.     memset(dist, 0x3f, sizeof dist);    // 起点不能到达其他点，距离为无穷
  16.     dist[s] = 0;
  17.     p = P(0, s);
  18.     q.push(p);
  19.     while (!q.empty()) {
  20.         p = q.top();
  21.         q.pop();
  22.         int x = p.second;
  23.         if (vis[x]) {
  24.             continue;
  25.         }
  26.         vis[x] = true;
  27.         for (int i=0; i<g[x].size(); ++i) {
  28.             p = g[x][i];
  29.             int y = p.second, w = p.first;
  30.             if (dist[y] > dist[x] + w) {
  31.                 dist[y] = dist[x] + w;
  32.                 q.push(P(dist[y], y));
  33.             }
  34.         }
  35.     }
  36. }
  37. int main() {
  38.     cin >> n >> m;
  39.     for (int i=0; i<m; ++i) {
  40.         int x;
  41.         cin >> x;
  42.         cin >> p.second >> p.first;
  43.         g[x].push_back(p);
  44.     }
  45.     dj(1);
  46.     if (dist[n] != 0x3f3f3f3f) {
  47.         cout << dist[n] << endl;
  48.     } else {
  49.         cout << -1 << endl;
  50.     }
  51.     return 0;
  52. }

时间复杂度：5.8.4 最短路 - 图1#card=math&code=O%28m%5Clog%20m%29&id=yS0gr)，5.8.4 最短路 - 图2 为边数。

代码中 memset 语句填入了 0x3f ，这意味着把数组的每一位设成 0x3f，最终把整个数组初始化为无穷大 0x3f3f3f3f。类似地，memset 有三种优雅的初始化赋值方案:

  1. memset(vis, 0, sizeof vis);        // 初始化为 0
  2. memset(ans, -1, sizeof ans);    // 初始化为 -1
  3. memset(dist, 0x3f, sizeof dist);    // 初始化为 0x3f3f3f3f

使用 memset 语句初始化数组，具有比 for 循环赋值更高的效率。

5.8.4.2 SPFA

支持负权图，可检测环的单源最短路 “快速算法” 。Bellman-Ford 算法的队列优化形式，在中国多称为SPFA（Shortest Path Faster Algorithm）。

  1. // SPFA
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N = 1e5 + 4;
  5. const int inf = 0x3f3f3f3f;
  6. struct Edge {
  7.     int y, w;    // 终点，边权
  8.     Edge() {}
  9.     Edge(int a, int b): y(a), w(b) {}
  10. } e;
  11. vector<Edge> g[N];
  12. int dist[N];
  13. bool vis[N];
  14. int cnt[N];
  15. queue<int> q;
  16. int n, m;
  17. // s 为起点，返回 true 时表示有环路
  18. void spfa(int s) {
  19.     memset(dist, 0x3f, sizeof dist);
  20.     dist[s] = 0;
  21.     q.push(s);
  22.     while (!q.empty()) {
  23.         int x = q.front();
  24.         q.pop();
  25.         vis[x] = false;
  26.         for (int i=0; i<g[x].size(); ++i) {
  27.             e = g[x][i];
  28.             int y = e.y;
  29.             int w = e.w;
  30.             if (dist[y] > dist[x] + w) {
  31.                 dist[y] = dist[x] + w;
  32.                 cnt[y] = cnt[x] + 1;
  33.                 if (cnt[y] >= n) return true;
  34.                 if (!vis[y]) {
  35.                     q.push(y);
  36.                     vis[y] = true;
  37.                 }
  38.             }
  39.         }
  40.     }
  41.     return false;
  42. }
  43. int main() {
  44.     cin >> n >> m;
  45.     for (int i=0; i<m; ++i) {
  46.         int x, y, w;
  47.         cin >> x >> y >> w;
  48.         g[x].push_back(Edge(y, w));
  49.     }
  50.     spfa(1);
  51.     if (dist[n] == inf) {
  52.         cout << "impossible" << endl;
  53.     } else {
  54.         cout << dist[n] << endl;
  55.     }
  56.     return 0;
  57. }

平均时间复杂度：5.8.4 最短路 - 图3#card=math&code=O%28km%29&id=tBx9B) ，5.8.4 最短路 - 图4 为一个小常数，5.8.4 最短路 - 图5 为边数。

最坏时间复杂度：5.8.4 最短路 - 图6#card=math&code=O%28nm%29&id=lxEYV) ，5.8.4 最短路 - 图7 为边数。

SPFA 在题目告知无环的情况，可以不写 cnt[] 及关联代码。这个算法在一般的非负权图上经常可以有胜过 Dijkstra 算法的效率，但最坏情况下（出题人有意制造针对数据）会超时。关于这一趣闻，可以参阅网上资料 「关于SPFA，它死了」。

5.8.4.3 Floyd 算法

全源最短路算法，可求任意两个结点之间的最短路，唯一弱点是不能处理负环。在稠密图的情况下，时间复杂度优于 5.8.4 最短路 - 图8 次 Dijkstra 算法。因此，模板的实现使用了邻接矩阵存储图，需要注意初始化和防止重边。

// Floyd Shortest Path
#include <iostream>
#include <cstring>
using namespace std;
const int N = 300;
int g[N][N];
int n, m;
int main() {
    cin >> n >> m;
    // init
    memset(g, 0x3f, sizeof g);
    for (int i=0; i<n; ++i) {
        g[i][i] = 0;
    }
    // Read
    for (int i=0; i<m; ++i) {
        int x, y, w;
        cin >> x >> y >> w;
        g[x][y] = min(g[x][y], w);  // 防止重边
    }
    // Floyd
    for (int k=0; k<n; ++k) {
        for (int i=0; i<n; ++i) {
            for (int j=0; j<n; ++j) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    // Print
    for (int i=0; i<n; ++i) {
        for (int j=0; j<n; ++j) {
            cout << g[i][j] << ',';
        }
        cout << endl;
    }
    return 0;
}

时间复杂度：5.8.4 最短路 - 图9#card=math&code=O%28n%5E3%29&id=sbjQS)， 5.8.4 最短路 - 图10 为点数。

Floyd 算法的核心其实就是三层 for 循环，内部的语句也很好理解——如果从 5.8.4 最短路 - 图11 点通过 5.8.4 最短路 - 图12 点再到 5.8.4 最短路 - 图13 点，比直接到 5.8.4 最短路 - 图14 点更近，则把 5.8.4 最短路 - 图15，5.8.4 最短路 - 图16 两点距离 5.8.4 最短路 - 图17 更新。然而这三层循环的层次，循环变量的改变方向绝不那么简单。事实上，它是一种「动态规划」的思想。我们会在后文进行讨论。

练习：蓝桥 算法训练 最短路