题目描述
给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。
再给定k个询问,每个询问包含两个整数x和y,表示查询从点x到点y的最短距离,如果路径不存在,则输出“impossible”。
数据保证图中不存在负权回路。
算法:floyd算法
时间复杂度:$O(N^3)$
需要注意
(1)floyd求的是多元汇最短路方案
(2)floyd算法可以解决出现负权边的情况,但是无法解决负权回路的情况
(3)三重循环的顺序:先枚举k,i和j的顺序任意
(4)需要对自己本身的距离进行初始化(主要是因为floyd是基于动态规划 动态规划的成立需要对状态进行初始化)
(5)由于使用邻接矩阵进行存图,最后判断需要判断成INF/2(邻接矩阵是可以更新不存在的边的)
C++代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=210;
const int INF=0x3f3f3f3f;
int d[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++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
memset(d,0x3f,sizeof d);
for(int i=1;i<=n;i++)d[i][i]=0;
for(int i=0;i<m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
d[a][b]=min(d[a][b],c);
}
floyd();
for(int i=0;i<k;i++){
int a,b;
scanf("%d%d",&a,&b);
if(d[a][b]>INF/2)cout<<"impossible"<<endl;
else cout<<d[a][b]<<endl;
}
return 0;
}