【多源最短路】Floyd算法求最短路

题目描述

给定一个 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≤n≤200, 1≤k≤n2 1≤m≤20000, 图中涉及边长绝对值均不超过 10000。

输入样例：

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

输出样例：

impossible 1

算法思路：

本质：动态规划思想

1.初始化距离数组d[][] ①初始时所有两点间距离为正无穷大 ②自己到自己的距离要初始化为0 ③读入设置两点间的边权值（注意因为可能存在重边,所以要取边权的最小值） 2.用k，i，j去更新d[i][j]（三重循环实现） 用一个中间点k，比较路径d[i,k]+d[k,j]与路径d[i,j]谁更小，谁距离更短

时间复杂度：O(n的3次方) 适用情况：多源最短路，即任意两点间的距离

画图理解：

AC代码：

#include <iostream>
#include <cstring>
using namespace std;

const int N=210,INF=1e9;

int n,m,q;

int d[N][N];
//二、用k，i，j去更新d[i][j]
//用一个中间点k，比较路径d[i,k]+d[k,j]与路径d[i,j]谁更小，谁距离更短
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>>q;

    //一、初始化
    memset(d, 0x3f, sizeof d);//①所有两点间距离为正无穷大
    //注意：memset函数是对字节为单位进行赋值的，赋值成0x3f作为无穷大来使用
    for(int i=1;i<=n;i++) d[i][i]=0;//②自己到自己的距离要初始化为0

    /*
    前两步初始化也可以用以下循环实现
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
    */
    while(m--)
    {
          
   
        int x,y,z;
        cin>>x>>y>>z;
        d[x][y]=min(d[x][y],z);//③读入设置两点间的边权值，注意因为可能存在重边,所以要取边权的最小值
    }

    floyd();

    while(q--)//执行操作
    {
          
   
        int x,y;
        cin>>x>>y;
        if(d[x][y]>INF/2) cout<<"impossible"<<endl;
        /*注意：x，y不连通，他们之间的值也可能不是正无穷大。
        因为两点之间可能有到中间点的距离是负边权，加上之后就<正无穷大了。
        所以x,y之间不连通时，只需判断让其>一个较大的数即可。
        */
        else cout<<d[x][y]<<endl;
    }



}