三角形最短路径问题

#include <bits/stdc++.h>

using namespace std;

int arr[100][100] = {0}, temp[100][100] = {0}, pre[100][100] = {0}, n;

void dp(int &col) {
    temp[0][0] = arr[0][0];
    //第一列
    for (int i = 1; i < n; i++)
        temp[i][0] = temp[i - 1][0] + arr[i][0], pre[i][0] = 0;

    //对角线
    for (int i = 1; i < n; i++)
        temp[i][i] = temp[i - 1][i - 1] + arr[i][i], pre[i][i] = i - 1;

    for (int i = 2; i < n; i++)
        for (int j = 1; j < i; j++)
            temp[i - 1][j - 1] < temp[i - 1][j] ? (temp[i][j] = temp[i - 1][j - 1] + arr[i][j], pre[i][j] = j - 1)
                                                : (temp[i][j] = temp[i - 1][j] + arr[i][j], pre[i][j] = j);

    int final = temp[n - 1][0];
    for (int i = 1; i < n; i++)
        if (final > temp[n - 1][i])
            final = temp[n - 1][i], col = i;
    printf("%d\n", final);

}

void path(int col) {
    deque<int> d;
    for (int i = n - 1; i >= 0; i--)
        d.emplace_back(arr[i][col]), col = pre[i][col];

    for (auto it = d.rbegin(); it != d.rend(); it++) {
        if (it != d.rbegin())
            printf(" ");
        printf("%d", *it);
    }

}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i + 1; j++)
            scanf("%d", &arr[i][j]);
    int col;
    dp(col);
    path(col);

    return 0;
}