http://https://ac.nowcoder.com/acm/problem/52867
- 题目大意
有n个城市，城市之间有n-1条无向道路。Bob在任意两个城市之间建造高速公路的花费是这两个城市之间的最短路径的长度，现在Bob想用最昂贵的方式建造n-1条高速公路使n个城市联通，问最昂贵的费用是多少 - 以最昂贵的方式建造一条高速公路，就是两个城市之间的最短路最大，这个最大的最短路就是树的直径，然后再把其他点连接到这个直径的端点（距离更远的那一个端点），这样建高速公路就是最昂贵的。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,c;
int v1,v2,h;
int cnt;
struct ty1{
int st;
int to;
int len;
int next;
}edge[200010];
int head[200010];
struct ty2{
int num;
ll dist;
bool operator<(const ty2 &a) const{
return dist>a.dist;
}
};
void add(int x,int y,int z){
edge[++cnt].st =x;
edge[cnt].to = y;
edge[cnt].len = z;
edge[cnt].next = head[x];
head[x] = cnt;
}
ll dis1[200010];
ll dis2[200010];
int vis[200010];
priority_queue<ty2> q;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
ty2 dij(int st,ll dis[]){
while(!q.empty()) q.pop();
memset(vis,0,sizeof(vis));
for(int i = 1;i<=n;i++) dis[i] = 1e18;
dis[st] = 0;
q.push({st,0});
long long max = -1;
int k = 0;
while(!q.empty()){
auto fr = q.top();
q.pop();
int nu = fr.num;
ll d = fr.dist;
if(vis[nu]) continue;
vis[nu] = 1;
if(max<d&&d!=1e18) max = d,k = nu;
for(int i = head[nu];i!=-1;i = edge[i].next){
if(vis[edge[i].to]||edge[i].len+d>dis[edge[i].to]) continue;
dis[edge[i].to] = edge[i].len+d;
q.push({edge[i].to,dis[edge[i].to]});
}
}
return {k,max};
}
int main(){
while(cin>>n){
cnt = 0;
memset(head,-1,sizeof(head));
for(int i = 1;i<=n-1;i++){
v1 = read();
v2 = read();
h = read();
add(v1,v2,h);
add(v2,v1,h);
}
ll ans = 0;
int a = dij(1,dis1).num;//找到直径的一个端点a
ty2 c = dij(a,dis1);//通过端点a请确定另一个端点b,同时跑一次最短路，确定树上的节点到a的最短路
int b = c.num;
dij(b,dis2);//从端点b跑一次最短路，确定树上的节点到b的最短路
ans += c.dist;
for(int i = 1;i<=n;i++){
if(i==a||i==b) continue;
//连接距离远的端点
if(dis1[i]>=dis2[i]) ans+=dis1[i];
else ans+=dis2[i];
}
cout<<ans<<endl;
}
}