#pragma warning(disable:4996)
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define MAXN 10005

using namespace std;

struct Edge {
	int d, w;
	Edge(int destination, int weight)
		:d(destination), w(weight) { }
};
vector<Edge> G[MAXN];
void addEdge(int s, int d, int w) {
	G[s].push_back(Edge(d, w));
}

int longest[MAXN], longestLeaf[MAXN], root = 1, n = 1;

void search(int father, int now) {
	for (size_t i = 0;i < G[now].size();++i)
		if (G[now][i].d != father) search(now, G[now][i].d);
	priority_queue<int> pq;
	for (size_t i = 0;i < G[now].size();++i)
		if (G[now][i].d != father) pq.push(G[now][i].w + longestLeaf[G[now][i].d]);

	if (!pq.empty()) {
		longestLeaf[now] = pq.top();
		longest[now] = longestLeaf[now];
		pq.pop();
	}
	if (!pq.empty()) longest[now] += pq.top();
}

int main(int argc, char *argv[]) {
	int s, d, w;
	while (scanf("%d%d%d", &s, &d, &w) == 3)
		addEdge(s, d, w), addEdge(d, s, w), ++n;
	search(-1, root);
	int longestRoute = longest[root];
	for (int i = 1;i <= n - 1;++i) 
		longestRoute = max(longestRoute, longest[i]);
	printf("%d\n", longestRoute);
}

• Re:为什么要记录次长QwQ (185) suncongbo 2017-11-25 22:54:48