2123.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2123 on 2005-10-22 at 18:10:04 */ 
#include <cstdio>
#include <cstring>

const int MAX = 1024;
const long INFINITE = 10240000;

typedef struct {
	int path[MAX];
	int n;
	long d[MAX];
} List;


List cross[MAX];
long d[MAX];
long n[MAX];
bool walk[MAX];

int main()
{
	int N, M;
	int i, j, x, y, mini;
	long min, p;

	while(scanf("%d", &N) == 1) {
		if(N == 0) {
			return 0;
		} else {
			scanf("%d", &M);
			for(i = 1; i <= N; i++) {
				cross[i].n = 0;
				walk[i] = false;
				d[i] = INFINITE;
				n[i] = 0;
			}
			for(i = 0; i < M; i++) {
				scanf("%d %d %ld", &x, &y, &p);
				cross[x].path[cross[x].n] = y;
				cross[y].path[cross[y].n] = x;
				cross[x].d[cross[x].n++] = cross[y].d[cross[y].n++] = p;
			}
			for(i = 0; i < cross[2].n; i++) {
				d[cross[2].path[i]] = cross[2].d[i];
				n[cross[2].path[i]] = 1;
			}
			walk[2] = true;
			d[2] = 0;
			while(true) {
				min = INFINITE;
				for(j = 1; j <= N; j++) {
					if(!walk[j] && d[j] < min) {
						min = d[j];
						mini = j;
					}
				}
				if(min == INFINITE || mini == 1) {
					break;
				}
				walk[mini] = true;
				for(j = 0; j < cross[mini].n; j++) {
					if(!walk[cross[mini].path[j]]) {
						if(d[mini] < d[cross[mini].path[j]]) {
							n[cross[mini].path[j]] += n[mini];
						}
						if(cross[mini].d[j] + d[mini] < d[cross[mini].path[j]]) {
							d[cross[mini].path[j]] = cross[mini].d[j] + d[mini];
						}
					}
				}
			}
			printf("%ld\n", n[1]);
		}
	}
	
	return 0;
}