HDU 1385 Minimum Transport Cost 最短路径题解

本题就是使用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;
}