mod_n7_v12

#include <iostream>
#include <limits.h>
#include <algorithm>
#include <vector>

using namespace std;

const int n = 10;

int mtx[n][n] = {
    {0, 0, 3, 2, 0, 0, 0, 0, 0, 0},
    {0, 0, 4, 2, 1, 0, 0, 0, 0, 0},
    {0, 0, 0, 0, 0, 4, 0, 2, 0, 0},
    {0, 0, 0, 0, 0, 4, 0, 2, 5, 0},
    {0, 0, 0, 0, 0, 0, 2, 4, 0, 0},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 3},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 4},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 2},
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 3},
};
int dp1[n];
int dp2[n];

int main() {
    dp1[0] = 0;
    dp2[1] = 0;
    for (int i = 2; i < n; ++ i) {
        int mn = 10000;
        for (int j = i - 1; j >= 0; -- j) {
            if (mtx[j][i] != 0 && j != 1)
                mn = min(mn, dp1[j] + mtx[j][i]);
        }
        dp1[i] = mn;
    }
    int x = n - 1;
    vector<int> v;
    v.push_back(x);
    while (x != 0) {
        //printf("%d\n", x);
        for (int i = 0; i < n; ++ i) {
            if (dp1[x] == dp1[i] + mtx[i][x]) {
                x = i;
                break;
            }
        }
        v.push_back(x);
    }
    printf("1:\n");
    printf("dp:");
    for (int i = 0; i < n; ++ i)
        printf(" %d", dp1[i]);
    printf("\n");
    reverse(v.begin(), v.end());
    printf("way:");
    for (int i = 0; i < v.size(); ++ i) {
        printf(" %d", v[i] + 1);
    }
    printf("\n\n");


    for (int i = 2; i < n; ++ i) {
        int mn = 10000;
        for (int j = i - 1; j > 0; -- j) {
            if (mtx[j][i] != 0)
                mn = min(mn, dp2[j] + mtx[j][i]);
        }
        dp2[i] = mn;
    }
    x = n - 1;
    v.clear();
    v.push_back(x);
    while (x != 1) {
        for (int i = 1; i < n; ++ i) {
            if (dp2[x] == dp2[i] + mtx[i][x]) {
                x = i;
                break;
            }
        }
        v.push_back(x);
    }
    printf("2:\n");
    printf("dp:");
    for (int i = 0; i < n; ++ i)
        printf(" %d", dp2[i]);
    printf("\n");
    reverse(v.begin(), v.end());
    printf("way:");
    for (int i = 0; i < v.size(); ++ i) {
        printf(" %d", v[i] + 1);
    }
    printf("\n");
    return 0;
}