Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

为什么要记录次长QwQ

Posted by CuriousCat at 2016-08-27 13:19:15 on Problem 2631
#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);
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator