floyd 是一个求多源最短路问题，可以存在负环。时间复杂度是$O(n^3)$, 基本思路是基于动态规划的。
算法的而基本流程：
1
2
3
4
| for k <- 1 to n:
for i <- 1 to n:
for j <- 1 to n:
g[i][j] = min(g[i][j], g[i][k] + g[k][j])
|
AcWing 854. Floyd求最短路
来源: https://www.acwing.com/problem/content/856/
给定一个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≤n^2,$
$1≤m≤20000,$
图中涉及边长绝对值均不超过10000。
输入样例：
1
2
3
4
5
6
| 3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
|
输出样例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int g[N][N];
int n, m, w;
int main()
{
memset(g, 0x3f, sizeof g);
cin >> n >> m >> w;
while(m--)
{
int a, b, c;
cin >> a >> b >> c;
g[a][b] = min(g[a][b], c);
}
for (int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if (i == j)
g[i][j] = 0;
for(int k = 1; k <= n; k++)
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]);
while(w--)
{
int a, b;
cin >> a >> b;
if (g[a][b] > INF / 2) puts("impossible");
else cout << g[a][b] << endl;
}
return 0;
}
|