HDU 1385 Minimum Transport Cost 最短路徑題解

本題就是使用Floyd算法求所有路徑的最短路徑，並且需要保存路徑，而且更進一步需要按照字典順序輸出結果。

還是有一定難度的。

Floyd有一種很巧妙的記錄數據的方法，大多都是使用這個方法記錄數據的。

不過其實本題數據不是很大，一般太大的數據也無法使用Floyd，因為效率是O(N^3)。

所以其實也可以使用一般的Floyd算法，然後增加個三維數組記錄數據。下面就是這種做法，0ms過了.

#include 
#include 
using std::vector;

vector checkDictOrder(vector a, vector 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 > &gra, vector &tax,
			    vector > > &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 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 > gra(N, vector(N));
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				scanf("%d", &gra[i][j]);
			}
		}
		vector tax(N);
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &tax[i]);
		}

		vector > > paths(N, vector >(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;
}