Floyd

Floyd 是一个多源最短路算法。

输入样例：

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

输出样例：

impossible
1

// AcWing 805
#include<bits/stdc++.h>
using namespace std;

int dp[205][205];
const int INF = 1e9; // 不要使用INT_MAX 将导致溢出
int n,m,k,x,y,z;

void floyd(){
    for(int k = 1;k <= n;k++){ // 注意先枚举k
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                dp[i][j] = min(dp[i][j],dp[i][k] + dp[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)dp[i][j] = 0;
            else dp[i][j] = INF;
        }
    }

    // 输入x,y,z
    for(int i = 1;i <= m;i++){
        cin>>x>>y>>z;
        dp[x][y] = min(dp[x][y],z);
    }

    floyd();

    for(int i = 1;i <= k;i++){
        cin>>x>>y;
        if(dp[x][y] > INF/2)cout<<"impossible"<<endl; //由于有负权边存在所以约大过INF/2也很合理
        else cout<<dp[x][y]<<endl; // 直接输出dp[x][y]即可
    }
    return 0;
}