C++

$\color{#cc33ff}{— > 算法基础课题解}$

思路：

floyd 最短路

$图解：$

闫氏DP分析法：

                    集合：所有从i到j，且只经过1 ~ k作为中间点的路径的集合

        状态表示
        f[k][i][j]        
                    属性：最短距离
DP

        状态计算                f[k][i][j]
                    中间点含k：f[k - 1][i][k] + f[k - 1][k][j]
                    中间点不含k：f[k - 1][i][j]

状态转移方程：f[k][i][j] = min(f[k - 1][i][j], f[k - 1][i][k] + f[k - 1][k][j])
              f[i][j] = min(f[i][j], f[i][k] + f[k][j])

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;

int n, m, k;
int d[N][N];

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 >> k;

    for (int i = 1; i <= n; i ++) // 初始化
        for (int j = 1; j <= n; j ++)
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

    while (m --) {
        int a, b, w;
        cin >> a >> b >>w;

        d[a][b] = min(d[a][b], w); // 如果有多条边，保存最小的边
    }

    floyd();

    while (k --) {
        int a, b;
        cin >> a >> b;

        if (d[a][b] > INF / 2) cout << "impossible" << endl;
        else cout << d[a][b] << endl;
    }

    return 0;
}