Floyd

⬅ 返回

1、算法分析

2、例题

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

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

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

3、代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define PI 3.14159
using namespace std;
 
typedef pair<int,int> PII;
typedef long long LL;
const int MAX_INT =  0x3f3f3f3f;
const int N = 1e3+15;
const int mod = 1e9+7;
 
int n; 
int g[N][N];//邻接表
 
 
void floyd()
{
    for(int k=1;k<=n;k++)//k一定要放在最外层 i j 不要求
    {
        for(int i=1;i<=n;i++)
    	{
		    for(int j=1;j<=n;j++)
		    {
				g[i][j]=min(g[i][j],g[i][k]+g[k][j]);//对邻接表进行更新
		    }
	    }
        
    }
}
 
void solve()
{
	int m,k;
	cin>>n>>m>>k;
	memset(g,0x3f,sizeof g);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i==j)g[i][j]=0;//这里要把所有顶点到自身的距离设为0 因为是多源汇 有多个顶点
	while(m--)
	{
		int x,y,z;
		cin>>x>>y>>z;
		g[x][y]=min(g[x][y],z);
	}
	floyd();
	
	while(k--)
	{
		int x,y;
		cin>>x>>y;
		//这里也不是等于MAX_INT 因为最大值也会被负权变更新
		if(g[x][y]>=MAX_INT/2)cout<<"impossible"<<endl;
		else cout<<g[x][y]<<endl;
	}
	
 
}
 
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
    int T = 1;
    while(T--)
    {
        solve();
    }
}