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