学步园

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

Dijsktra算法：

伪代码：

清除所有标记

d[0] = 0, 其他d[i] = intmax

for (1到n) {

所有没有标记的点中寻找d[i]最小的点x

标记x

对以x出发的点进行更新所有边（x,y)  即：d[y] = min( d[y], d[x]+map[x][y] )

}

//Dijkstra算法的应用
#include <iostream>
using namespace std;

const int MAX = 201;
const int intmax = 10000000;
int Map[MAX][MAX];
int dist[MAX];
bool visited[MAX];
int n, m, s, e;
int i, j;
void Dijsktra()
{
	for (i = 0; i < n; i++) dist[i] = Map[s][i];
	dist[s] = 0;
	visited[s] = 1;
	for (i = 0; i < n; i++) {
		int x = s, m = intmax;
		for (j = 0; j < n; j++) 
			if (!visited[j] && dist[j]<=m)
				m = dist[x=j];
		visited[x] = 1;
		for (j = 0; j < n; j++) {//更新
			dist[j] = min(dist[j], dist[x]+Map[x][j]);
		}
	}
}
int main()
{
	int a, b, cost;	
	while (cin >> n >> m) {
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++) {
				if (i == j) Map[i][j] = 0;
				else Map[i][j] = intmax;
		}
		for (i = 0; i < m; i++) {
			cin >> a >> b >> cost;
			if (cost < Map[a][b]) {//要处理重路
				Map[a][b] = cost;
				Map[b][a] = cost;
			}
		}
		cin >> s >> e;//起点和终点
		memset (visited, 0, sizeof(visited));
		for (i = 0; i < MAX; i++)
			dist[i] = intmax;
		Dijsktra();
		if (dist[e] == intmax) cout << -1 << endl;
		else cout << dist[e] << endl;
	}
	return 0;
}