53 lines
1.5 KiB
C++
53 lines
1.5 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
int n;
|
||
int a[101][101] = {0};
|
||
int f[101];
|
||
|
||
int main() {
|
||
//输入+输出重定向
|
||
freopen("../1279.txt", "r", stdin);
|
||
cin >> n;
|
||
for (int i = 1; i <= n; i++) {
|
||
for (int j = 1; j <= n; j++) {
|
||
cin >> a[i][j];
|
||
}
|
||
}
|
||
//问：从编号为 1 的城市到编号为n 的城市之间的最短距离是多少？
|
||
//思路：从最后一个城市，反向构建，
|
||
for (int i = 1; i <= n; i++) {
|
||
f[i] = a[n][i] > 0 ? a[n][i] : 9999; //复制最后一行，做为动态规划的起始数据
|
||
}
|
||
for (int i = 1; i <= n; i++) {
|
||
cout << f[i] << " ";
|
||
}
|
||
cout << endl;
|
||
|
||
//动态规划的DP表定义：一维数组
|
||
//dp[x] 表示 x这个节点，到最后一个节点的最短距离
|
||
for (int i = n - 1; i >= 1; i--) { //从后向前，逐行递推
|
||
for (int j = 1; j <= n; ++j) { //逐列查找
|
||
if (a[i][j] > 0) {
|
||
// j表示从哪个节点，i表示到哪个节点,比如j=6,i=10，表示节点6到节点10的距离是a[i][j]=8
|
||
// 其实修改的就是dp[i][j]=a[i][j]+dp[i][n]
|
||
if (a[i][j] + f[j] < f[i]) {
|
||
f[i] = a[i][j] + f[j];
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
for (int i = 1; i <= n; i++) {
|
||
cout << f[i] << " ";
|
||
}
|
||
cout << endl;
|
||
|
||
//输出结果
|
||
cout << f[1];
|
||
//关闭文件
|
||
fclose(stdin);
|
||
return 0;
|
||
}
|