1436.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1436 on 2006-04-21 at 22:09:47 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int SN = 128;
const int INF = 1 << 30;

int cast[SN][SN];

int dijkstra(int, int);

int main()
{
	int n, i, j;
	
	while(scanf("%d", &n) != EOF) {
		for(i = 0; i < n; i++) cast[i][i] = 0;
		for(i = 1; i < n; i++)
			for(j = 0; j < i; j++) {
				int d; char ch; scanf("\n%c", &ch);
				if(ch == 'x') d = INF;
				else { ungetc(ch, stdin); scanf("%d", &d); }
				cast[i][j] = cast[j][i] = d;
			}
		printf("%d\n", dijkstra(0, n));
	}
	
	return 0;
}

int dijkstra(int src, int n)
{
	int i, j, d[SN]; bool vst[SN];
	for(i = 0; i < n; i++) { d[i] = INF; vst[i] = false; }
	d[0] = 0; int last = 0;
	for(i = 0; i < n; i++) {
		int mind = INF, mini;
		for(j = 0; j < n; j++)
			if(!vst[j] && mind > d[j]) { mind = d[j]; mini = j; }
		if(mind == INF) break;
		last = mind; vst[mini] = true;
		for(j = 0; j < n; j++) d[j] = min(d[j], d[mini]+cast[mini][j]);
	}
	return last;
}