狗狗40题搞完纪念 » 1022

1022
1022.cpp


#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 512;
const int INF = 0x7f7f7f7f;

int main() {
	int ri = 0, n, m;
	bool mark[MAXN];
	int e[MAXN][MAXN], mind[MAXN];

	while (scanf("%d%d", &n, &m) != EOF && n > 0) {
		for (int i = 0; i < n; ++i) {
			mark[i] = false;
			mind[i] = INF;
			for (int j = 0; j < n; ++j) {
				e[i][j] = INF;
			}
		}
		for (int i = 0; i < m; ++i) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			--a;
			--b;
			e[a][b] = e[b][a] = c;
		}

		mind[0] = 0;
		for (int i = 0; i < n; ++i) {
			int k = -1;
			for (int j = 0; j < n; ++j) {
				if (!mark[j] && (k == -1 || mind[j] < mind[k])) {
					k = j;
				}
			}
			mark[k] = true;
			for (int j = 0; j < n; ++j) {
				if (!mark[j] && mind[j] > mind[k] + e[k][j]) {
					mind[j] = mind[k] + e[k][j];
				}
			}
		}

		double ans = 0;
		int x = 0, y = -1;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				if (e[i][j] < INF) {
					double a = min(mind[i], mind[j]);
					double b = max(mind[i], mind[j]) - a;
					if (b >= e[i][j]) {
						if (ans < a + b) {
							ans = a + b;
							x = mind[i] > mind[j] ? i : j;
							y = -1;
						}
					} else {
						if (ans < a + (e[i][j] + b) / 2) {
							ans = a + (e[i][j] + b) / 2;
							x = i;
							y = j;
						}
					}
				}
			}
		}

		printf("System #%d\nThe last domino falls after %.1lf seconds, ", ++ri, ans);
		if (y == -1) {
			printf("at key domino %d.\n\n", x + 1);
		} else {
			printf("between key dominoes %d and %d.\n\n", x + 1, y + 1);
		}
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//289 	2010-06-27 05:33:59 	Accepted 	1022 	C++ 	10 	180 	anotherpeg 	Source
Leave a Reply