python/TangDou/XiTi/1279.cpp

#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;
}