比赛 不平凡的世界 评测结果 AAAAAAAAAA
题目名称 不平凡的引线 最终得分 100
用户昵称 膜拜神犇王梦迪 运行时间 0.834 s
代码语言 C++ 内存使用 2.00 MiB
提交时间 2015-11-05 11:48:45
显示代码纯文本
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int kN = 1e5+10;
const int INF = 1e9+10;
int N;
vector<pair<int, int> > G[kN];
int d[kN], vis[kN];
int main() {
	freopen("firelead.in", "r", stdin);
	freopen("firelead.out", "w", stdout);
	scanf("%d", &N);
	N++;
	for (int i = 2; i <= N; i++) {
		int u, v, c; scanf("%d %d %d", &u, &v, &c);
		G[u].push_back(make_pair(v, c));
		G[v].push_back(make_pair(u, c));
	}
	
	priority_queue<pair<int, int> > q;
	for (int i = 1; i <= N; i++) {
		if (G[i].size() == 1) {
			q.push(make_pair(0, i));
			d[i] = 0;
		} else {
			d[i] = INF;
		}
	}
	while (q.size()) {
		int u = q.top().second;
		q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int i = 0; i < G[u].size(); i++) {
			int v = G[u][i].first, c = G[u][i].second;
			if (d[v] > d[u]+c) {
				d[v] = d[u]+c;
				q.push(make_pair(-d[v], v));
			}
		}
	}
	
	double ans = 0;
	for (int i = 1; i <= N; i++) {
		for (int j =0; j < G[i].size(); j++) {
			int v = G[i][j].first;
			double c = G[i][j].second;
			double mi = min(d[i], d[v]), mx = max(d[i], d[v]);
			// 整个引线烧完的时间 = 最近的点引燃 + 一个端点燃烧的时间 +  两个端点燃烧的时间 
			double tmp = mi + min(c, mx-mi) + (c-min(c, mx-mi))/2;
			ans = max(ans, max(mx, tmp));
		}
	}
	
	printf("%.1lf\n", ans);
	return 0;
}