#include<iostream>

using namespace std;

#define Inf 65536;

#define NIL -1;

int N = 5;  //假定图的节点有5个

int map[6][6];   //为方便，节点从1开始标号，该矩阵存储权重

int dist[6][6][6];

int path[6][6][6];

void Init()  //构建邻接矩阵

{

	for (int i = 1; i <= N; i++)

	{

		for (int j = 1; j <= N; j++)

		{

			if (i == j)

			{

				map[i][j] = 0;

			}

			else

				map[i][j] = Inf;

		}

	}

	map[1][2] = 3, map[1][3] = 8, map[1][5] = -4;

	map[2][4] = 1, map[2][5] = 7;

	map[3][2] = 4;

    map[4][1] = 2, map[4][3] = -5;

	map[5][4] = 6;

}

void Floyd_Warshall()

{

	for (int i = 1; i <= N; i++)

	{

		for (int j = 1; j <= N; j++)

		{

			dist[i][j][0] = map[i][j];

			path[i][j][0] = NIL;

		}

	}

	path[1][2][0] = 1, path[1][3][0] = 1, path[1][5][0] = 1;

	path[2][4][0] = 2, path[2][5][0] = 2;

	path[3][2][0] = 3;

	path[4][1][0] = 4, path[4][3][0] = 4;

	path[5][4][0] = 5;

	for (int k = 1; k <= N; k++)

	{

		for (int i = 1; i <= N; i++)

		{

			for (int j = 1; j <= N; j++)

			{

				if (dist[i][j][k - 1] <= dist[i][k][k - 1] + dist[k][j][k - 1])

				{

					dist[i][j][k] = dist[i][j][k - 1];

					path[i][j][k] = path[i][j][k - 1];

				}

				else

				{

					dist[i][j][k] = dist[i][k][k - 1] + dist[k][j][k - 1];

					path[i][j][k] = path[k][j][k - 1];

				}

			}

		}

	}

}

void Printf_Path(int path[6][6][6], int i, int j)

{

	if (i == j)

		cout << i << " ";

	else if (path[i][j][N] == -1)

	{

		cout << "NO path from " << i << " to " << j << "exists" << endl;

	}

	else

	{

		Printf_Path(path, i, path[i][j][N]);

		cout << j << " ";

	}

}

int main()

{

	Init();

	Floyd_Warshall();

	for (int k = 0; k <= N; k++)

	{

		for (int i = 1; i <= N; i++)

		{

			for (int j = 1; j <= N; j++)

			{

				cout << dist[i][j][k] << " ";

			}

			cout << endl;

		}

		cout << endl;

	}

	for (int k = 0; k <= N; k++)

	{

		for (int i = 1; i <= N; i++)

		{

			for (int j = 1; j <= N; j++)

			{

				cout << path[i][j][k] << " ";

			}

			cout << endl;

		}

		cout << endl;

	}

	Printf_Path( path, 1, 4);

	return 0;

}