时间限制:5.0s 内存限制:256.0MB
给定\(n\)个结点两两之间的单向边的长度,求两两之间的最短路径。
输入第一行包含一个整数\(n\),表示点数。
接下来\(n\)行,每行包含\(n\)个整数,第\(i\)行表示第\(i\)个点到每个点的边的长度,如果没有边,则用\(0\)表示。
输出\(n\)行,第\(i\)行表示第\(i\)个点到其他点的最短路径长度,如果没有可达的路径,则输出\(-1\)。
3 0 1 0 0 0 6 0 2 0
0 1 7 -1 0 6 -1 2 0
\(1\leq n\leq 1000\),\(0<\)边长\(\leq 10000\)。
\(a_{ij} 表示\)i\(到\)j\(之间的边长,当\)i\(到\)j$之间没有变时取无限大.
\(f_{kij}\) 表示\(i\)到\(j\)允许使用节点\(1~k\)作为中间节点.
目标:\(f_{nij}\)
初值:\(f_{0ij} = a_{ij}\) 表示从\(i\)到\(j\)不允许经过其他节点作为中间节点,所以\(i\)到\(j\)的距离就是\(a_{ij}\)。
转移方程:$f_{kij} = min(f_{k-1ij}, f_{k-1ik} + f_{k-1kj})
不用k点作为中间节点 用
因为用三维数组内存超大,需要优化
可以压缩一个维度————k
可以使用滚动数组,只需f[2][n][n],大大减小了数组内存占用
于是f[k % 2][i][j] = min(f[(k - 1) % 2][i][j], f[(k - 1) % 2][i][k] + f[(k - 1) % 2][k][j])
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int INF = 1e9; int a[1005][1005]; int f[2][1005][1005]; int main(int argc, char** argv) { int n; cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { cin >> a[i][j]; if (a[i][j] != 0) f[0][i][j] = a[i][j]; else if (i != j) f[0][i][j] = INF; } for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[k % 2][i][j] = min(f[(k - 1) % 2][i][j], f[(k - 1) % 2][i][k] + f[(k - 1) % 2][k][j]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (f[n % 2][i][j] == INF) cout << -1 << " "; else cout << f[n % 2][i][j] << " "; } cout << endl; } return 0; }