1236.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1236 on 2006-03-08 at 10:45:42 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 512;
const int INF = 1 << 30;

double last;
bool one;
int domino[MAX][MAX], n, key[2];

void dijkstra(int);

int main()
{
	int m, i, t;
	
	for(t = 1; scanf("%d %d", &n, &m) != EOF && n != 0; t++) {
		memset(domino, -1, sizeof(domino));
		for(i = 0; i < m; i++) {
			int a, b, d; scanf("%d %d %d", &a, &b, &d);
			domino[a-1][b-1] = domino[b-1][a-1] = d;
		}
		dijkstra(0);
		printf("System #%d\nThe last domino falls after %.1lf seconds, ", t, last);
		if(one) printf("at key domino %d.\n\n", key[0]+1);
		else printf("between key dominoes %d and %d.\n\n", key[0]+1, key[1]+1);
	}
	
	return 0;
}

void dijkstra(int src)
{
	int d[MAX], i, j; bool vst[MAX] = { false };
	for(i = 0; i < n; i++) d[i] = INF;
	d[src] = 0; last = -INF;
	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; }
		vst[mini] = true;
		if(last < d[mini]) {
			one = true; last = d[mini]; key[0] = mini;
		}
		for(j = 0; j < n; j++)
			if(domino[mini][j] == -1) continue;
			else if(vst[j] && d[j]+domino[mini][j] > d[mini]) {
				double cost = (d[j]+domino[mini][j]+d[mini]) / 2.0;
				if(cost > last) {
					last = cost; one = false;
					key[0] = min(mini, j); key[1] = max(mini, j);
				}
			} else d[j] = min(d[j], d[mini]+domino[mini][j]);
	}
}