#include <fstream.h>
#include <string.h>

const int NODENUM = 25;
typedef  char	str[NODENUM+1];
void GetThePath (int [], str [], int [NODENUM][NODENUM]);

int main ()
{
	int			edges[NODENUM][NODENUM];
	ifstream	edgeIn;
	char		begin;
	char		end;
	char		dest;
	int			node;
	int			row;
	int			col;
	int			times;
	int			distance[NODENUM];
	str			path[NODENUM];
	str			first;
	str			second;
	int			original;
	int			shortest;
	int			nextshortest;
	int			length;

	edgeIn.open("network.txt");

	for (row = 0; row < NODENUM; row++)
		for (col = 0; col < NODENUM; col++)
			edges[row][col] = 1000;

	edgeIn >> begin >> end >> length;
	while (edgeIn)
	{
		row = begin - 'A';
		col = end - 'A';
		edges[row][col] = edges[col][row] = length;
		edgeIn >> begin >> end >> length;
	}
	cout <<  "Enter destination node: ";
	cin >> dest;
	while (dest != '.')
	{
	node = dest - 'A';
	GetThePath (distance, path, edges);
	strcpy(first, path[node]);
	shortest = distance[node];
	nextshortest = 1000;
	for (times = 0; times < strlen(first)-1; times++)
	{
		row = first[times] - 'A';
		col = first[times+1] - 'A';
		original = edges[row][col];
		edges[row][col] = edges[col][row] = 1000;
		GetThePath(distance, path, edges);
		if (distance[node] < nextshortest)
		{
			nextshortest = distance[node];
			strcpy(second, path[node]);
		}
		edges[row][col] = edges[col][row] = original;
	}
	cout << "The fastest route from A to " << dest << " is "
		<< first << " with a delay of " << shortest << endl;
	cout << "The second fastest route from A to " << dest << " is "
		<< second << " with a delay of " << nextshortest << endl;
	cout <<  "\nEnter destination node: ";
	cin >> dest;
	}
	return 0;
}

void GetThePath (int distance[], str  path[], int  edges[NODENUM][NODENUM])
{
	int		row;
	int		col;
	int		times;
	char	addon[2] = " ";

	for (row = 0; row < NODENUM; row++)
	{
		strcpy(path[row],"A");
		distance[row] = 1000;
	}
	distance[0] = 0;
	for (times = 0; times < NODENUM; times++)
		for (row = 0; row < NODENUM; row++)
			if (distance[row] < 1000)
				for (col = 0; col < NODENUM; col++)
					if (distance[row]+edges[row][col] < distance[col])
					{
						distance[col] = distance[row] + edges[row][col];
						addon[0] = char (col + 'A');
						strcpy(path[col],path[row]);
						strcat(path[col],addon);
					}
	return;
}