多源最短路（floyd）

floyd

就是很简单很简单的一种dp

3个for循环就出结果

看代码就可以知道，floyd就是通过遍历可能会出现i-j比i-k+k-j大的情况，很简单。

贴一个水题http://codevs.cn/problem/1077/

floyd考的话也是和其他算法一起考

一般情况下由于floyd的本质，n方的邻接链表矩阵反而更有效率。

#include<cstdio>
using namespace std;
int map[ + ][ + ];
int n,q,a,b;
void floyd()
{
    for(int k = ;k <= n;k ++)//中间点
        for(int i = ;i <= n;i ++)//起点
            for(int j = ;j <= n;j ++)//终点
                if(map[i][k] + map[k][j] < map[i][j])//这里就是更新
                map[i][j] = map[i][k] + map[k][j];
}
int main()
{
    scanf("%d",&n); 
    for(int i = ;i <= n;i ++)
        for(int j = ;j <= n;j ++)
            scanf("%d",&map[i][j]);
    scanf("%d",&q);
    floyd();
    while(q --)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",map[a][b]);
    }
}
           

可以通过floyd求最小环

int mincircle = INF;
for(int k = ;k <= n;k ++)
    for(int i = ;i <= n;i ++)
        for(int j = ;j <= n;++ j)
        {
            if(dis[i][j] != INF && map[j][k] != INF && mao[k][i] != INF 
            &&dis[i][j] + map[j][k] + map[k][i] < mincircle)
            mincircle = min(mincircle,dis[i][j] + map[j][k] + mao[k][i]);//严格n3方，还是tarjan好。
        }