学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2544

Dijkstra算法应用

#include <iostream>
using namespace std;

const int intmax = 10000000;
const int MAX = 102;
int Map[MAX][MAX];
bool visited[MAX];
int dist[MAX];
int n, m;
void Dijsktra()
{
	int i, j;
	for (i = 1; i <= n; i++)
		dist[i] = Map[1][i];
	visited[1] = 1;
	dist[1] = 0;
	for (j = 1; j <= n; j++) {
		int x = 1, m = intmax;
		for (i = 1; i <= n; i++) //寻找最短路
			if (!visited[i] && dist[i] < m)
				m = dist[x=i];
		visited[x] = 1;
		for (i = 1; i <= n; i++)//更新
			if (!visited[i] && Map[x][i] < intmax)
				dist[i] = min(dist[i], dist[x]+Map[x][i]);
	}
}
int main ()
{
	int a, b, cost;
	int i, j;
	while (cin >> n >> m && (n+m)) {
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++) {
				if (i == j) Map[i][j] = 0;
				else Map[i][j] = intmax;
			}
		while (m--) {
			cin >> a >> b >> cost;
			if (cost < Map[a][b]) {//防止重路
				Map[a][b] = cost;
				Map[b][a] = cost;
			}
		}
		memset (visited, 0, sizeof(visited));
		for (i = 1; i <= n; i++)
			dist[i] = intmax;
		Dijsktra();//从1到各点的最短路径
		cout << dist[n] << endl;	
	}
	return 0;
}