多源最短路Floyd本质理解

\(Floyd\)总结复习

Floyd是动态规划的典型体现，其思想从集合角度用闫氏DP分析法即可

其关键的性质理解：即外层循环k的理解。

\(dist[k][i][j]\)代表（k的取值范围是从1到n），在考虑了从1到k的节点作为中间经过的节点时，从i到j的最短路径的长度。

那么就可以发现\(Floyd\)具有明显的递增性，就可以应用到删除边或者一条条加边的题目中

举个例子，比如，dist[1][i][j]就代表了，在考虑了1节点作为中间经过的节点时，从i到j的最短路径的长度。
dist[3][i][j] 表示考虑1~3这三个节点作为中间的中转节点，从i到j的最短路

从具体到抽象的话: dist[k][i][j] 可以从两种情况转移而来：

1. 从\(dist[k−1][i][j]\)转移而来，表示i到j的最短路径不经过k这个节点
2. 从\(dist[k−1][i][k]+dist[k−1][k][j]\)转移而来，表示i到j的最短路径经过k这个节点

那么我们总结就是： dist[k][i][j]=min(dist[k−1][i][j],dist[k−1][i][k]+dist[k−1][k][j]) 发现dist[k]只可能与dist[k−1]有关。 那么我们就可以利用滚动数组的思想，去掉k这个维度。

模板题复习

给定一个 $ n $ 个点 $ m $ 条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定 $ k $ 个询问，每个询问包含两个整数 $ x $ 和 $ y $，表示查询从点 $ x $ 到点 $ y $ 的最短距离，如果路径不存在，则输出 impossible。

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数 $ n,m,k $。

接下来 $ m $ 行，每行包含三个整数 $ x,y,z $，表示存在一条从点 $ x $ 到点 $ y $ 的有向边，边长为 $ z $。

接下来 $ k $ 行，每行包含两个整数 $ x,y $，表示询问点 $ x $ 到点 $ y $ 的最短距离。

输出格式

共 $ k $ 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。

数据范围

$ 1 \le n \le 200 \(, \) 1 \le k \le n^2 $
$ 1 \le m \le 20000 $,
图中涉及边长绝对值均不超过 $ 10000 $。

输入样例：

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

输出样例：

impossible
1

#include <bits/stdc++.h>
using namespace std;
const int N = 210;
int dist[N][N];
int n,m,k;
void floyd()
{
    for (int k=1;k<=n;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]);
}
int main()
{
    cin>>n>>m>>k;
    memset(dist,0x3f,sizeof dist);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (i==j)
                dist[i][j]=0;
    while (m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        dist[a][b]=min(dist[a][b],c);
    }
    
    floyd();
    while (k--)
    {
        int a,b;
        cin>>a>>b;
        if (dist[a][b]>=0x3f3f3f3f/2) puts("impossible");
        else cout<<dist[a][b]<<endl;
    }
    
    return 0;
}