九度OJ 108 HDOJ 3790:最短経路問題ディジェストラアルゴリズム

1979 ワード

c アルゴリズムテスト System IM

浙大のこの大学院受験の上で機題は明らかに最短経路アルゴリズムを使うことを並べて、時間の複雑さを考慮して、私はディジェストラアルゴリズムを使いました.
この問題は本のサンプルアルゴリズムよりやや複雑で,要求距離が最も短いだけでなく,同時に複数の距離が最も短い場合にも要求費用が最も短い.この処理の方法は,最短パスを更新する際に2つのケースを考慮することである.HDOJのテストデータには重辺があるので、入力時には最短の重辺を保存します.
私のACコード:

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;

const int Max = 1000 + 10;
int dist[Max][Max];
int cost[Max][Max];
int minDist[Max];
int minCost[Max];
const int Inf = 0x0fffffff;
int n, m;

void Dijkstra(int source)
{
	bool final[Max] = {false};

	for(int i=1; i<=n; ++i) 
		minDist[i] = dist[source][i], minCost[i] = cost[source][i], final[i] = false;
	final[source] = true;

	for(int i=2; i<=n; ++i)
	{
		int pos = 1, md = Inf, mc = Inf;

		for(int j=1; j<=n; ++j)
			if(!final[j] && ((minDist[j] < md) || (minDist[j] == md && minCost[j] < mc)))
				md = minDist[j], pos = j, mc = minCost[j];

		if(md == Inf) break;
		final[pos] = true;

		for(int j=1; j<=n; ++j)
			if(!final[j] && ((minDist[pos] + dist[pos][j] < minDist[j]) || (minDist[pos] + dist[pos][j] == minDist[j] && minCost[pos] + cost[pos][j] < minCost[j])))
				minDist[j] = minDist[pos] + dist[pos][j], minCost[j] = minCost[pos] + cost[pos][j];
	}
}

int main()
{
	int a, b, c, d;
	int head, tail;

	while(scanf("%d %d", &n, &m) && !(!n && !m))
	{
		for(int i(0); i<Max; ++i)
			for(int j(0); j<Max; ++j) dist[i][j] = cost[i][j] = Inf;

		for(int i(0); i<m; ++i)
		{
			scanf("%d %d %d %d", &a, &b, &c, &d);

			//    
			if(dist[a][b] > c || (dist[a][b] == c && cost[a][b] > d))
			{
				dist[a][b] = dist[b][a] = c;
				cost[a][b] = cost[b][a] = d;
			}
		}

		scanf("%d %d", &head, &tail);
		Dijkstra(head);
		printf("%d %d
", minDist[tail], minCost[tail]);
	}
	system("pause");
	return 0;
}

【9章】Javaを学ぼう

【8章】Javaを学ぼう