Highway |
||
| Accepted : 78 | Submit : 275 | |
| Time Limit : 4000 MS | Memory Limit : 65536 KB | |
HighwayIn ICPCCamp there were n towns conveniently numbered with 1,2,…,n connected with (n−1) roads. The i -th road connecting towns ai and bi has length ci . It is guaranteed that any two cities reach each other using only roads. Bobo would like to build (n−1) highways so that any two towns reach each using only highways. Building a highway between towns x and y costs him δ(x,y) cents, where δ(x,y) is the length of the shortest path between towns x and y using roads. As Bobo is rich, he would like to find the most expensive way to build the (n−1) highways. InputThe input contains zero or more test cases and is terminated by end-of-file. For each test case: The first line contains an integer n . The i -th of the following (n−1) lines contains three integers ai , bi and ci .
OutputFor each test case, output an integer which denotes the result. Sample Input5 Sample Output19 |
//题意:有一棵树，问所有点到这棵树中所有点最远距离和为多少
//因为这个是树，所以，从任意一点 dfs 搜最远点，再从最远点 dfs 搜最远点，再dfs一下，这样，保存了2个最远点到任意点的距离，遍历一遍选最大的那个即可，最后减去直径，因为重复算了一次
一共就 4 n 次遍历吧，1800 ms 还行吧
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f3f3f3f3f
#define MX 100005
struct To
{
int to;
LL c;
}; int n;
int far;
LL step;
vector<To> road[MX];
LL dis[][MX]; void Init()
{
for (int i=;i<=n;i++)
road[i].clear();
} void dfs(int x,int pre,LL s,int kk)//所在位置，从前，距离，第几次
{
if (kk!=) dis[kk-][x]=s; if (s>step)
{
far=x;
step=s;
}
for (int i=;i<(int)road[x].size();i++)
{
if (road[x][i].to!=pre)
dfs(road[x][i].to,x,road[x][i].c+s,kk);
}
} int main()
{
while (~scanf("%d",&n))
{
Init();
for (int i=;i<n-;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
road[a].push_back((To){b,c});
road[b].push_back((To){a,c});
} step=;
dfs(,,,); step=;
dfs(far,,,);
step=;
dfs(far,,,); LL ans = ;
for (int i=;i<=n;i++)
ans += max(dis[][i],dis[][i]);
ans -= step;
printf("%I64d\n",ans);
}
return ;
}