1653.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1653 on 2005-11-06 at 19:22:57 */ 
#include <cstdio>

const int MAX = 1024;

class List {
public:
	int path[MAX];
	int link[MAX];
	int n;
};

List list[MAX];
int n;

int Dijkstra(int, int);
inline int max(int, int);
inline int min(int, int);

int main()
{
	int t, T;
	int m, x, y, d;
	int i;
	
	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		scanf("%d %d", &n, &m);
		for(i = 1; i <= n; i++) {
			list[i].n = 0;
		}
		for(i = 0; i < m; i++) {
			scanf("%d %d %d", &x, &y, &d);
			list[x].link[list[x].n] = y;
			list[y].link[list[y].n] = x;
			list[x].path[list[x].n++] = list[y].path[list[y].n++] = d;
		}
		printf("Scenario #%d:\n", t);
		printf("%d\n\n", Dijkstra(1, n));
	}
	
	return 0;
}

int Dijkstra(int src, int dis)
{
	int d[MAX] = {0}, m, maxi = src;
	bool visit[MAX] = {false};
	int i, j, p;

	for(i = 0; i < n; i++) {
		m = 0;
		for(j = 0; j < n; j++) {
			if(m < d[j] && !visit[j]) {
				m = d[j];
				maxi = j;
			}
		}
		visit[maxi] = true;
		for(j = 0; j < list[maxi].n; j++) {
			if(!visit[list[maxi].link[j]]) {
				if(d[maxi] == 0) {
					p = list[maxi].path[j];
				} else {
					p = min(d[maxi], list[maxi].path[j]);
				}
				d[list[maxi].link[j]] = max(p, d[list[maxi].link[j]]);
			}
		}
		if(maxi == dis) {
			break;
		}
	}
	return d[dis];
}
inline int max(int n, int m)
{
	return n > m ? n : m;
}
inline int min(int n, int m)
{
	return n < m ? n : m;
}