Floyd算法

区别于之前介绍过的接种算法，Floyd算法是求解的多源的最短路问题。

Floyd算法的流程

枚举顶点 k ∈ [1 , n]

​ 以顶点k作为中介点，枚举所有顶点对i 和 j（i ∈ [1 , n] , j ∈ [1 , n]）

​ 如果dis [i ,k] + dis[k , j] < dis[i , j] 成立

​ 赋值dis[i , j] = dis [i ,k] + dis[k , j]

​ _出自《算法笔记》

值得注意的是

(1) 最外层的k循环不能放到里面去，因为假如后面的d[i , j]得到了优化，那么前面的d[i , j]会由于无法得到再次遍历而无法更新；

(2) Floyd算法中不能存在负权回路，因为有负权回路的图无解，这样的话将会导致无解。

(3) 由于解决的是不存在负权回路的问题，所以，其回路都是正数，那么存在自环的话就直接舍弃掉就好了；对于有多条边的就和之前的朴素版的dijkstra算法一样取最小的一条即可。

代码及注释

#include<iostream>
#include<cstring>
using namespace std;
const int N=210;
int dist[N][N];
int n,m,k;

void floyd(){
    for(int k=1;k<=n;k++){//注意k循环的顺序不能放到里面去
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);//用k做中介，来跟新i,j之间的距离
            }
        }
    }

}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    memset(dist,0x3f,sizeof dist);
    for(int i=0;i<=n;i++) dist[i][i]=0;//对于自环直接处理为0

    while(m--){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);;
        dist[x][y]=min(dist[x][y],z);//假如x,y之间有重边那么只取最小的那一条
    }

    floyd();

    while(k--){
        int x,y;
        scanf("%d%d",&x,&y);
        if(dist[x][y]>0x3f3f3f3f/2) puts("impossible");//由于有负权边,所以判断条件为dist[x][y]>0x3f3f3f3f/2
        else printf("%d\n",dist[x][y]);
    }
    return 0;
}