mod_n9_v18

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

using namespace std;

const int n = 11;
int mtx[n][n] = {
    { 0,  3,  0,  0,  0,  0,  0,  0,  0,  0,  0},
    { 0,  0,  9,  7, 10,  0,  0,  0,  0,  0,  0},
    { 0,  0,  0,  0,  0, 17,  0,  0,  0,  0,  0},
    { 0,  0,  0,  0,  0,  0,  0,  0, 28,  0,  0},
    { 0,  0,  0,  6,  0,  0,  0, 17,  0,  0,  0},
    { 0,  0,  0,  0,  0,  0, 14,  0,  0,  4,  0},
    { 0,  0,  0,  0,  0,  0,  0,  0,  0, 10,  0},
    { 0,  0,  0,  0,  0,  0,  0,  0,  0,  8,  0},
    { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1},
    { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1},
    { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0},
};

int tp[n];
int tn[n];
int R[n];

int T(int a, int b) {
    return mtx[a][b];
}

void TN(int i) {
    int mn = INT_MAX;
    for (int j = 0; j < n; ++ j) {
        if (T(i, j) != 0) {
            if (tn[j] == -1)
                TN(j);
            mn = min(mn, tn[j] - T(i, j));
        }
    }
    tn[i] = mn;
}

int main(void) {
    printf("tp:");
    for (int i = 1; i < n; ++ i) {
        int mx = INT_MIN;
        for (int j = 0; j < n; ++ j) {
            if (T(j, i) != 0)
                mx = max(mx, tp[j] + T(j, i));
        }
        tp[i] = mx;
        printf(" %d", tp[i]);
    }
    printf("\n");
    for (int i = 0; i < n; ++ i)
        tn[i] = -1;
    tn[n - 1] = tp[n - 1];
    for (int i = n - 2; i >= 0; -- i) {
        TN(i);
    }
    printf("tn:");
    for (int i = 0; i < n; i ++) {
        printf(" %d", tn[i]);
    }
    printf("\n");

    printf("R:");
    for (int i = 0; i < n; ++ i) {
        R[i] = tn[i] - tp[i];
        printf(" %d", R[i]);
    }
    printf("\n");

    printf("critical way:");
    int x = 0;
    while (x != n - 1) {
        for (int i = x; i < n; ++ i) {
            if (T(x, i) != 0 && R[i] == 0) {
                printf(" %d", x + 1);
                x = i;
                break;
            }
        }
    }
    printf(" %d\n", n);

    printf("\n");
    for (int i = 0; i < n; ++ i) {
        for (int j = i; j < n; ++ j) {
            if (T(i, j) != 0) {
                printf("Rn(%d,%d) = %d\n", i + 1, j + 1, tn[j] - tp[i] - T(i, j));
            }
        }
    }
    printf("\n");
    for (int i = 0; i < n; ++ i) {
        for (int j = i; j < n; ++ j) {
            if (T(i, j) != 0) {
                printf("Rc(%d,%d) = %d\n", i + 1, j + 1, tp[j] - tp[i] - T(i, j));
            }
        }
    }
    return 0;
}