40 lines
1.2 KiB
C++
40 lines
1.2 KiB
C++
// 教学模板：有向图，无负环。输入 n m，随后 m 行 u v w。
|
|
// 输出 n 行最短距离矩阵，不可达写 INF。这个输出约定为教学自拟。
|
|
// 建议教学数据 n<=500、|w|<=10^9，有限路长和候选之和远小于 INF。
|
|
#include <algorithm>
|
|
#include <iostream>
|
|
#include <vector>
|
|
using namespace std;
|
|
using ll = long long;
|
|
const ll INF = 1LL << 60;
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(false);
|
|
cin.tie(nullptr);
|
|
int n, m;
|
|
cin >> n >> m;
|
|
vector<vector<ll>> d(n + 1, vector<ll>(n + 1, INF));
|
|
for (int i = 1; i <= n; ++i) d[i][i] = 0;
|
|
for (int t = 0; t < m; ++t) {
|
|
int u, v;
|
|
ll w;
|
|
cin >> u >> v >> w;
|
|
d[u][v] = min(d[u][v], w);
|
|
}
|
|
for (int k = 1; k <= n; ++k)
|
|
for (int i = 1; i <= n; ++i)
|
|
for (int j = 1; j <= n; ++j) {
|
|
if (d[i][k] == INF || d[k][j] == INF) continue;
|
|
ll nd = d[i][k] + d[k][j];
|
|
d[i][j] = min(d[i][j], nd);
|
|
}
|
|
for (int i = 1; i <= n; ++i) {
|
|
for (int j = 1; j <= n; ++j) {
|
|
if (j > 1) cout << ' ';
|
|
if (d[i][j] == INF) cout << "INF";
|
|
else cout << d[i][j];
|
|
}
|
|
cout << '\n';
|
|
}
|
|
}
|