费洛伊德算法（求路径）怎么做呀？

常规
1

时间限制：1s 空间限制：512M

题目描述：

用费洛伊德（Floyd）算法求任意两点最短路径。

分别输出给定两对结点最短路径值，并依次列出其路径结点。

输入格式：

第一行二个整数 �1,�1s1,t1；

第二行二个整数 �2,�2s2,t2；

第三行二个整数 �,�n,m；(�≤ 200,\ �≤ 40000)(n≤ 200,\ m≤ 40000)

随后 m 行每行三个整数 �,�,�a,b,c，表示 a, b 之间有一条权值为 �c 的边。(�≤ 109)(c≤ 109)

输出格式：

s1 到 t1 的最短路，并输出路径（按字典序输出最小的一条）

s2 到 t2 的最短路，并输出路径（按字典序输出最小的一条）

样例输入：

1 3
2 5
5 7
1 2 6
1 4 2
1 5 23
2 3 4
2 4 3
3 4 20
3 5 7

样例输出：

9
1 4 2 3
11
2 3 5

这题怎么做呀，哪位大神来解答一下？

1 个赞
6

Floyd算法就是通过 我所认为的暴力 来找最大值。

P1359 租用游艇 这题是Floyd（弗洛伊德）的模板题

给出代码：

#include <bits/stdc++.h>
using namespace std;
int a[210][210],n;
int main(){
    memset(a,0x7f,sizeof(a));
    cin >> n;
    for (int i = 1;i <= n;i++)
        for (int j = i;j <= n;j++){
            if (i == j) a[i][j] = 0;
            else cin >> a[i][j];
        }
    for (int k = 1;k <= n;k++) for (int j = 1;j <= n;j++) for (int i = 1;i <= k;i++) a[i][j] = min(a[i][j],a[i][k] + a[k][j]);
    cout << a[1][n];
    return 0;
}

蒟蒻浅见，有什么错误还请指正

1 个赞
7

然后您的那道题作为蒟蒻的我还没想出来，非常抱歉

1 个赞