HDU 1385 Minimum Transport Cost最短パス問題解

この問題はFloydアルゴリズムを用いて全経路の最短経路を求め,経路を保存する必要があり,さらに辞書順に結果を出力する必要がある.
やはり難しいですね.
Floydには非常に巧みにデータを記録する方法があり、多くはこの方法でデータを記録している.
ただ、実は本題データはあまり大きくなく、一般的には大きすぎるデータでもFloydは使えません.効率はOですから(N^3).
したがって,実際には一般的なFloydアルゴリズムを用いて,3次元配列記録データを追加することもできる.以下はこのようなやり方で、0 msが過ぎた.

#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 :
Path: ", 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
Total cost : %d

", h+1, gra[g][h]);
		}
	}
	return 0;
}