(Floyd)算法是最短路算法里面最最简单的一个
(同时也是最最耗费空间和时间的一个)
(Floyd)算法的主体非常简单,就是一个二维数组(f):
(f)数组的含义也非常好理解,当然也非常暴力:
(f_{ij})表示从点 (i) 到点 (j) 路径的最小值
那么其实我们在不断循环的过程中,就可以通过类似于dp的转移方程就可以做到把所有点之间的最短路标记完成,即:
(f_{ij}=min(f_{ij},f_{ik}+f_{kj}))
注意数组一定要初始化为一个极大数(如0x7fffffff)
但是呢,循环的顺序必须要讲:必须是先循环(k),再循环(i),最后套(j)循环,为什么是这样呢,我们需要模拟一下:首先我们找到了(ij)两点,此时我们需要找到一个供计算最小值的跳板(即(k)),于是我们先循环这个跳板,(如果先把(k)确定下来就会造成从某一点出发永远无法再次回到以(i)为起点的路径中去,最优解也无法体现),这样这个跳板就能让所有答案过一便而不会漏掉一些点,而(ij)两点也就会重复地被循环查找。也就是第一重循环必须是(k)的循环,后两层一般是选择先(i)后(j),因为毕竟顶点先被查找嘛~
那么,代码就呼之欲出了:(P4779
#include<bits/stdc++.h>
using namespace std;
const int N=1001,INF=99999999;
int floyd[N][N],n,m,s;
int main()
{
cin>>n>>m>>s;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
floyd[i][j]=INF;
}
floyd[i][i]=0;
}
for(int i=1;i<=m;++i)
{
int a,b,c;
cin>>a>>b>>c;
floyd[a][b]=min(floyd[a][b],c);
}
for(int k=1;k<=n;++k)
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(i!=j&&j!=k&&floyd[i][k]+floyd[k][j]<floyd[i][j])
{
floyd[i][j]=floyd[i][k]+floyd[k][j];
}
}
}
}
for(int i=1;i<=n;++i)
{
cout<<floyd[s][i]<<' ';
}
return 0;
}
但由于(Floyd)着实太慢了(毕竟2020他死了R.I.P),只能承载1000以下的数(还极有可能会炸QAQ),所以例题很少,这里贴的代码以最短路模板为例,但是绝对(A)不了!
填坑第 (huge{1}) 站完成!!!