floyd求最短路模版

1. 动态规划思想
2. 图需要初始化为正无穷大
3. 三重循环更新最短路径长度

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 210, M = 200010, INF = 0x3f3f3f3f;
int g[N][N];
int n, m, k;

void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
}


int main() {
    cin >> n >> m >> k;
    memset(g, 0x3f, sizeof(g));
    for (int i = 1; i <= n; i++) g[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int a, b, v;
        scanf("%d%d%d", &a, &b, &v);
        g[a][b] = min(g[a][b], v);
    }
    floyd();
    while (k--) {
        int a, b;
        scanf("%d%d", &a, &b);
        if (g[a][b] > INF / 2) printf("impossible\n");
        else printf("%d\n", g[a][b]);
    }

    return 0;
}