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

int max(int a, int b) {
	return ((a > b) ? a : b);
}
int min(int a, int b) {
	return ((a < b) ? a : b);
}

const int n = 11;
int mtx[n][n] = {
	{ 0,  5,  0,  0,  0,  0,  0,  0,  0,  0,  0},
	{ 0,  0,  7,  7,  7,  0,  0,  0,  0,  0,  0},
	{ 0,  0,  0,  0,  0, 13,  0,  0,  0,  0,  0},
	{ 0,  0,  0,  0,  0,  0,  0,  0, 14,  0,  0},
	{ 0,  0,  0,  5,  0,  0,  0, 11,  0,  0,  0},
	{ 0,  0,  0,  0,  0,  0, 18,  0,  0,  4,  0},
	{ 0,  0,  0,  0,  0,  0,  0,  0, 10,  7,  0},
	{ 0,  0,  0,  0,  0,  0,  0,  0,  0, 11,  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},
};

/*const int n = 5;
int mtx[n][n] = {
	{0, 2, 4, 0, 0},
	{0, 0, 3, 9, 0},
	{0, 0, 0, 5, 0},
	{0, 0, 0, 0, 6},
	{0, 0, 0, 0, 0},
};*/

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

int T(int a, int b) {
	return mtx[a][b];
}
//Подсчёт tp
void ctp(int 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;
}
//Подсчёт tn
void ctn(int i) {
	int mn = INT_MAX;
	for (int j = 0; j < n; ++ j) {
		if (T(i, j) != 0) {
			if (tn[j] == -1)
				ctn(j);
			mn = min(mn, tn[j] - T(i, j));
		}
	}
	tn[i] = mn;
}
//Вывод Rn
void outrn() {
	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));
			}
		}
	}
}
//Вывод Rc
void outrc() {
	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));
			}
		}
	}
}
//Вычисление критического пути
int ccw(int i) {
	if (i == n - 1) {
		cw[0] = i;
		return 1;
	}
	for (int j = i; j < n; ++ j) {
		if (T(i, j) != 0 && R[j] == 0) {
			int r = ccw(j);
			cw[r] = i;
			return r + 1;
		}
	}
}

int main(void) {
	//tp
	for (int i = 1; i < n; ++ i) {
		ctp(i);
	}

	//tn
	for (int i = 0; i < n; ++ i)
		tn[i] = -1;
	tn[n - 1] = tp[n - 1];
	for (int i = n - 2; i >= 0; -- i) {
		ctn(i);
	}

	//R
	for (int i = 0; i < n; ++ i)
		R[i] = tn[i] - tp[i];


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

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

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

	printf("critical way:");
	int brd = ccw(0);
	for (int i = brd - 1; i >= 0; -- i) {
		printf(" %d", cw[i] + 1);
	}
	printf("\n");

	printf("\n");
	outrn();
	printf("\n");
	outrc();
	return 0;
}