[编程笔记]-Floyd

前言

你以为这篇最短路和其他最短路差了一天的时间吗？不，实际上只差了一个小时(ノへ￣、)

现在是00: 24

半夜三更发癫很正常，如有发癫您就别管那点鸡毛小事了hhh

作用

用于多源汇最短路问题，也就是有多个源点的最短路问题。

实现

1. 邻接矩阵存储所有的边
2. 直接上三重循环。啊就是找起点终点和跳板点然后通过跳板点更新dis嘛不想解释了看代码吧。

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

你以为它是暴力？哈哈哈其实别人是基于动规的hhh。

这才是它的本来面貌：
d[k][i][j]=d[k-1][i][k]+d[k-1][k][j]
然后大佬把第一维给优化掉了hhh

所以要先循环k的hhh

代码

其实模板上面已经给了，所以这里直接上例题吧。

AcWing854-Floyd求最短路

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

const int N=202;

int n,m,k;
int x,y,z;
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;
    memset(d,0x3f,sizeof(d));
    while(m--){
        cin>>x>>y>>z;
        d[x][y]=min(d[x][y],z);
    }
    for(int i=1;i<=n;i++)d[i][i]=0;
    floyd();
    while(k--){
        cin>>x>>y;
        if(d[x][y]>0x3f3f3f3f/2)cout<<"impossible";//防止原本到不了的元素之间的负边导致终点减少。
        else cout<<d[x][y];
        cout<<"\n";
    }
    return 0;
}

完结撒花o(￣︶￣)o