Floyd算法-创新互联

AcWing 854. Floyd求最短路 题目

https://www.acwing.com/problem/content/description/856/
给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出impossible。
数据保证图中不存在负权回路。

创新互联自2013年创立以来，先为福海等服务建站，福海等地企业，进行企业商务咨询服务。为福海企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。思路

Floyd算法：动态规划的思想

• 状态表示：f[k][i][j]表示考虑经过前k个点，从i到j的距离的最小值
• 状态计算：f[k][i][j]=f[k-1][i][k]+f[k-1][k][j]

空间可以优化掉一维：f[i][j]=f[i][k]+f[k][j]

代码

#includeusing namespace std;

typedef long long LL;

const int N=210,INF=0x3f3f3f3f;
int d[N][N];
int n,m,t;

int main()
{cin>>n>>m>>t;
	memset(d,0x3f,sizeof d);
	for(int i=1;i<=n;i++) d[i][i]=0;

	while(m--)
	{int a,b,c;
		cin>>a>>b>>c;
		d[a][b]=min(d[a][b],c);
	}
    //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]);

	while(t--)
	{int x,y;
		cin>>x>>y;
		if(d[x][y]>INF/2) cout<<"impossible"<

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

文章名称：Floyd算法-创新互联
本文来源：http://6mz.cn/article/hehcp.html