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