比赛 |
不平凡的世界 |
评测结果 |
AAAAAAAAAA |
题目名称 |
不平凡的引线 |
最终得分 |
100 |
用户昵称 |
AAAAAAAAAA |
运行时间 |
0.156 s |
代码语言 |
C++ |
内存使用 |
4.99 MiB |
提交时间 |
2017-09-05 20:36:44 |
显示代码纯文本
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#define MAXN 100010
#define INF 0x3f3f3f3f
using namespace std;
struct Edge {
int t, next, v;
}e[MAXN<<1];
int d[MAXN], head[MAXN], cnt, deg[MAXN], M, ans;
void Add_Edge(int from, int to, int val) {
e[++cnt].t = to; e[cnt].next = head[from]; head[from] = cnt; e[cnt].v = val;
e[++cnt].t = from; e[cnt].next = head[to]; head[to] = cnt; e[cnt].v = val;
}
queue<int>q;
bool vis[MAXN];
int x[MAXN], y[MAXN], z[MAXN];
int main() {
freopen("firelead.in", "r", stdin);
freopen("firelead.out", "w", stdout);
scanf("%d", &M);
for (int i = 1; i <= M; i++) {
scanf("%d%d%d", &x[i], &y[i], &z[i]);
deg[x[i]]++; deg[y[i]]++;
Add_Edge(x[i], y[i], z[i]);
}
int rt, ans = 0;
memset(d, INF, sizeof(d));
for (int i = 1; i <= M + 1; i++) { if (deg[i] == 1) { d[i] = 0; q.push(i); } }
while (!q.empty()) {
int u = q.front(); q.pop(); vis[u] = 0;
for (int i = head[u]; i; i = e[i].next) {
if (d[e[i].t] > d[u] + e[i].v) {
d[e[i].t] = d[u] + e[i].v;
if (!vis[e[i].t])q.push(e[i].t), vis[e[i].t] = 1;
}
}
}
for (int i = 1; i <= M; i++) {
ans = max(ans, d[x[i]] + d[y[i]] + z[i]);
}
//for (int i = 1; i <= M + 1; i++) {ans = max(ans, d[i]);}
printf("%.1lf", (double)ans / 2.0);
return 0;
}