比赛 |
不平凡的世界 |
评测结果 |
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;
}