Acwing.854 Floyd求最短路 (Floyd算法)

这篇具有很好参考价值的文章主要介绍了Acwing.854 Floyd求最短路 (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。

输入样例:

输出样例:

impossible
1

题解

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210，INF = 1e9;
int n, m,Q;
int d[N][N];
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，&Q);
	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 a, b, w;
		scanf("%d%d%d"，&a，&b，&w);
		d[a][b] = min(d[a][b], w);
	}
	floyd( );
	while (Q -- )
	{
		int a, b;
		scanf("%d%d"，&a，&b);
		if (d[a][b] >INF / 2) puts("impossible")
		else printf("%d", d[a][b]);
	}
	return 0;
}

题解

Floyd是一个简单的处理多源最短路径的方法，时间复杂度为O（n³）
Floyd模板就是

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]);
}