最短路算法-floyd算法
in Algorithm Pageviews
多源汇最短路常用算法—-Floyd算法
Floyd求最短路
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int floyd(int n)
{
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()
{
constexpr int N = 210;
constexpr int INF = 0x3f3f3f3f;
int d[N][N];
int n = 0, m = 0, q = 0;
cin >> 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;
cin >> a >> b >> w;
d[a][b] = min(d[a][b], w);
}
sol.floyd(n);
while (q--) {
int a = 0, b = 0;
cin >> a >> b;
if (d[a][b] > INF / 2) {
cout << -1 << endl;
} else {
cout << d[a][b] << endl;
}
}
return 0;
}