#include<iostream>
#include<iomanip>
#define NODE 20
#define INF 999
using namespace std;

double costMat[NODE][NODE];


//Cost matrix of the graph


double findV(double _y, double pmax = 0.02) {
	double p = 1;
	int v = 0;

	if (_y == 0){
		return v;
	}
	long double chisl = _y;
	long double sum = chisl;
	while (p > pmax) {
		v++;
		chisl = (chisl * _y)/v;
		sum += chisl;
		p = chisl/sum;
	}
	return v;
}

void floydWarshal() {
	double cost[NODE][NODE];    //defind to store shortest distance from any node to any node
	int next[NODE][NODE];
	double next1[NODE][NODE];
	double b[NODE][NODE];
	double v[NODE][NODE];
	int a[NODE][NODE];
	int b1[NODE][NODE];
	cout << " enter first matrix" << endl;
	for (int i = 0; i < NODE; i++) {
		for (int j = 0; j < NODE; j++) {
			cin >> costMat[i][j];
				if (costMat[i][j] == 0 && (i != j)) {
					costMat[i][j] = INF;
				}
		}
	}
	cout << " enter nagruzki" << endl;
	for (int i = 0; i < NODE; i++) {
		for (int j = 0; j < NODE; j++) {
			cin >> next1[i][j];
		}
	}

	for (int i = 0; i < NODE; i++) {
		for (int j = 0; j < NODE; j++) {
			b[i][j] = 0;
		}
	}


	for (int i = 0; i < NODE; i++)
		for (int j = 0; j < NODE; j++) {
			cost[i][j] = costMat[i][j];
		}

	for (int i = 0; i < NODE; i++)
		for (int j = 0; j < NODE; j++) {
			if(costMat[i][j] != INF)
			 next[i][j] = j;
			else{
				next[i][j] = -1;
			}
		}

	for (int k = 0; k < NODE; k++) {
		for (int i = 0; i < NODE; i++)
			for (int j = 0; j < NODE; j++)
				if (cost[i][k] + cost[k][j] < cost[i][j]) {
					cost[i][j] = cost[i][k] + cost[k][j];
					next[i][j] = next[i][k];
				}
	}


	for (int i = 0; i < NODE; i++) {
		for (int j = 0; j < NODE; j++) {
			int d = i;
			do {
				b[d][next[d][j]] += next1[i][j];
				d = next[d][j];
			} while (d != j);
		}
	}

	for (int i = 0; i < NODE; i++) {
		for (int j = 0; j < NODE; j++) {
			v[i][j] = findV(b[i][j]);
		}
	}

	for (int i = 0; i < NODE; i++) {
		for (int j = 0; j < NODE; j++) {
			a[i][j] = (int)(v[i][j] * 85600);
			if (a[i][j] != 0)b1[i][j] = a[i][j] + 16000;
			else b1[i][j] = 0;

		}
	}



	cout << "The matrix:" << endl;
	for (int i = 0; i < NODE; i++) {
			for (int j = 0; j < NODE; j++) {
				cout.precision(3);
				cout << cost[i][j] << " ";
			}
		cout << endl;
	}


	cout << "The matrix:" << endl;
	for (int i = 0; i < NODE; i++) {
		for (int j = 0; j < NODE; j++) {
			cout.precision(3);
			cout << setw(5) << b[i][j] << " ";
		}
		cout << endl;
	}


	cout << "The matrix v:" << endl;
	for (int i = 0; i < NODE; i++) {
		for (int j = 0; j < NODE; j++) {
			cout.precision(3);
			cout << setw(5) << v[i][j] << " ";
		}
		cout << endl;
	}

	cout << "The matrix a:" << endl;
	for (int i = 0; i < NODE; i++) {
		for (int j = 0; j < NODE; j++) {
			cout.precision(10);
			cout << setw(1) << a[i][j] << " ";
		}
		cout << endl;
	}
	cout << "The matrix b:" << endl;
	for (int i = 0; i < NODE; i++) {
		for (int j = 0; j < NODE; j++) {
			cout.precision(10);
			cout << setw(1) << b1[i][j] << " ";
		}
		cout << endl;
	}


	cout << " \n \n \n";
	for (int i = 0; i < NODE; i++) {
			for (int j = 0; j < NODE; j++) {
				cout << setw(5) << next[i][j] + 1;
			}
		cout << endl;
	}


}

int main() {
	floydWarshal();
}