$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

基于DP思想，$d_{i,j}$ 为 $i$ 到 $j$ 的最短路长度。
写个状态转移方程就没事了。
其中 $k$ 表示中转站。

#include <bits/stdc++.h>
using namespace std;
const int N = 210, M = 2e+10, INF = 0x3f3f3f3f;
int n, m, k, x, y, z;
int d[N][N];
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--) {

        cin>>x>>y>>z;
        d[x][y] = min(d[x][y], z);
    }
    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]);
    while (k--) {
        cin>>x>>y;
        if (d[x][y] > INF / 2) puts("impossible");
        else cout<<d[x][y]<<endl;
    }
}