最短路

单源最短路：

所有边权为正：朴素 dijkstra ($O(n^2)$)，适合稠密图；

​ 堆优化版 dijkstra ($O(m\log n)$) ，适合稀疏图。

1. $dist[1] = 0, dist[i] = +\infty$, $s[N]$: 已确定最短路的点
2. for i in 1~n: 循环

边权有负值：Bellman-Ford($O(nm)$)；SPFA 是前者的优化，平均复杂度 $O(m)$。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m, g[N][N];
int d[N], st[N];
int dijkstra(){
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for(int i = 1; i < n; i ++){// 重复 n - 1 次
        int x = -1;
        // 找到未标记节点中 dist 最小的
        for(int j = 1; j <= n; j ++){
            if(!st[j] && (x == -1 || d[x] > d[j])) x = j;
        }
        st[x] = 1; 
        // 用 x 作为中介更新其它节点
        for(int y = 1; y <= n; y ++) 
            d[y] = min(d[y], d[x] + g[x][y]);
    }
    if(d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}

int main() {
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    // for(int i = 1; i <= n; i ++) g[i][i] = 0; // 可省略
    for(int i = 0; i < m; i ++){
        int x, y, c; cin >> x >> y >> c;
        g[x][y] = min(g[x][y], c);
    }
    dijkstra();
    for(int i = 1; i < n; i ++) cout << d[i] << " ";
}

// 堆优化
typedef pair<int, int> pii;
const int N = 100010;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int d[N], st[N];

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int dijkstra(){
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    priority_queue<pii, vector<pii>, greater<pii>>pq;
    pq.push({0, 1});
    while(pq.size()){
        auto x = pq.top().second; pq.pop(); // auto t = pq.top();
        if(st[x]) continue;
        st[x] = 1;
        // 扫描所有出边
        for(int i = h[x]; i != -1; i = ne[i]){
            int y = e[i];
            if(!st[y] && d[y] > d[x] + w[i]){ // d[x] 换成 t.first 也可
            // if(d[y] > d[x] + w[i]) 也可
                d[y] = d[x] + w[i];
                pq.push({d[y], y});
            }
        }
    }
    if(d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}
int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++){
        int x, y, c; cin >> x >> y >> c;
        add(x, y, c);
    }
    dijkstra();
    for(int i = 1; i < n; i ++) cout << d[i] << " ";
}

// 有边数限制的最短路
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510, M = 10010;
int n, m, k;
int d[N], backup[N];
struct Edge{
    int a, b, w;
}edges[M];
int bellman_ford(){
    memset(d, 0x3f, sizeof d);
    for(int i = 0; i < k; i ++){
    	memcpy(backup, d, sizeof d);
        for(int j = 0; j < m; j ++){
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            d[b] = min(d[b], backup[a] + w);
        }
    }
    return d[n];
}
int main() {
    cin >> n >> m >> k;
    for(int i = 0; i < m; i ++){
        int a, b, w; cin >> a >> b >> w;
        edges[i] = {a, b, w};
	}
    int t = bellman_ford();
    if(t > 0x3f3f3f3f / 2) cout << "impossible" << endl;
    else cout << t;
}

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef pair<int, int> pii;
const int N = 1000010;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int d[N], st[N]; // st[] 表示是否在队列中

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
int spfa(){
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    queue<int>q;
    q.push(1);
    st[1] = 1;
    while(q.size()){
        int x = q.front(); q.pop();
        st[x] = 0;
        for(int i = h[x]; i != -1; i = ne[i]){
            int y = e[i];
            if(d[y] > d[x] + w[i]){
                d[y] = d[x] + w[i];
                if(!st[y]) q.push(y), st[y] = 1;
            }
        }
    }
    if(d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}
int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++){
        int x, y, c; cin >> x >> y >> c;
        add(x, y, c);
    }
    spfa();
    for(int i = 1; i < n; i ++) cout << d[i] << " ";
}

// 负环判断
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

typedef pair<int, int> pii;
const int N = 1000010;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int d[N], st[N]; // st[] 表示是否在队列中
int cnt[N]; // 最短路径经过的边的个数
void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa(){
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    queue<int>q;
    for(int i = 1; i <= n; i ++){
    	q.push(i);
    	st[i] = 1;
    }
    while(q.size()){
        int x = q.front(); q.pop();
        st[x] = 0;
        for(int i = h[x]; i != -1; i = ne[i]){
            int y = e[i];
            if(d[y] > d[x] + w[i]){
                d[y] = d[x] + w[i];
                cnt[y] = cnt[x] + 1;
                if(cnt[y] >= n) return true;
                if(!st[y]) q.push(y), st[y] = 1;
            }
        }
    }
    return false;
}
int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; i ++){
        int x, y, c; cin >> x >> y >> c;
        add(x, y, c);
    }
    
}

多源汇最短路(任意两点之间)：Floyd ($O(n^3)$)

const int N = 301;
int d[N][N], n, m;
void floyd(){
    for(int k = 1; k <= n; k ++){
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= n; j ++){
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}
int main() {
    cin >> n >> m;
    memset(d, 0x3f, sizeof d);
    for(int i = 1; i <= n; i ++) d[i][i] = 0;
    for(int i = 0; i < m; i ++){
        int a, b, w; cin >> a >> b >> w;
        d[a][b] = min(d[a][b], w);
    }
}

Q.E.D.