本题就是使用Floyd算法求全部路径的最短路径，并且须要保存路径，并且更进一步须要依照字典顺序输出结果。

还是有一定难度的。

Floyd有一种非常巧妙的记录数据的方法，大多都是使用这种方法记录数据的。

只是事实上本题数据不是非常大，一般太大的数据也无法使用Floyd，由于效率是O(N^3)。

所以事实上也能够使用一般的Floyd算法，然后添加个三维数组记录数据。以下就是这样的做法，0ms过了.

#include <stdio.h>

#include <vector>

using std::vector;

vector<int> checkDictOrder(vector<int> a, vector<int> b)

{

	for (int i = 0; i < (int)a.size() && i < (int)b.size(); i++)

	{

		if (a[i] < b[i]) return a;

		else if (a[i] > b[i]) return b;

	}

	return a.size() < b.size() ? a : b;

}

void FloydWarshall(vector<vector<int> > &gra, vector<int> &tax,

			    vector<vector<vector<int> > > &paths)

{

	int N = (int)gra.size();

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

	{

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

		{

			if (-1 != gra[i][j])

			{

				paths[i][j].push_back(i);

				paths[i][j].push_back(j);

			}

		}

	}

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

	{

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

		{

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

			{

				if ( -1 != gra[i][k] && -1 != gra[k][j] &&

					(-1 == gra[i][j] ||

					gra[i][k] + gra[k][j] + tax[k] <= gra[i][j]))

				{

					vector<int> t = paths[i][k];

					t.pop_back();//pop k out

					t.insert(t.end(), paths[k][j].begin(), paths[k][j].end());

					if (gra[i][k]+gra[k][j]+tax[k]==gra[i][j])

						paths[i][j] = checkDictOrder(t, paths[i][j]);

					else paths[i][j] = t;

					gra[i][j] = gra[i][k] + gra[k][j] + tax[k];

				}

			}

		}

	}

}

int main()

{

	int N, g, h;

	while (scanf("%d", &N) && N)

	{

		vector<vector<int> > gra(N, vector<int>(N));

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

		{

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

			{

				scanf("%d", &gra[i][j]);

			}

		}

		vector<int> tax(N);

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

		{

			scanf("%d", &tax[i]);

		}

		vector<vector<vector<int> > > paths(N, vector<vector<int> >(N));

		FloydWarshall(gra, tax, paths);

		while (scanf("%d %d", &g, &h) && g != -1 && h != -1)

		{

			printf("From %d to %d :\nPath: ", g, h);

			g--, h--;

			if(g != h)

			{

				for (int u = 0; u+1 < (int)paths[g][h].size(); u++)

				{

					printf("%d-->", paths[g][h][u]+1);

				}

			}

			printf("%d\nTotal cost : %d\n\n", h+1, gra[g][h]);

		}

	}

	return 0;

}