本文最后更新于 1163 天前,其中的信息可能已经有所发展或是发生改变。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 100000
int arr[100][100];
int n;
int f(int v0){
int s[100];
int path[100];
int dist[100];
for(int i=0;i<n;i++){
if(arr[v0][i]==INF){
dist[i]=0;
}else{
dist[i]=arr[v0][i];
}
s[i]=0;
if(dist[i]!=INF){
path[i]=v0;
}else{
path[i]=-1;
}
}
s[v0]=1;
for(int i=1;i<n;i++){
int MAX=0;
int u=v0;
for(int j=0;j<n;j++){
if(dist[j]!=INF&&s[j]==0&&dist[j]>MAX){
MAX=dist[j];
u=j;
}
}
//cout<<"MAX:"<<MAX<<"u:"<<u<<endl;
s[u]=1;
for(int j=0;j<n;j++){
if(s[j]==0&&arr[j][u]!=INF&&arr[j][u]+dist[u]>dist[j]){
dist[j]=arr[j][u]+dist[u];
path[j]=u;
//cout<<"path "<<j<<"="<<u<<endl;
}
}
}
int temp=0;
for(int i=0;i<n;i++){
if(dist[i]>temp){
temp=dist[i];
}
}
//cout<<"temp:"<<temp<<endl;
return temp;
}
int main(){
cin>>n;
memset(arr,0,sizeof(arr));
for(int i=1;i<n;i++){
int x,y,v;
cin>>x>>y>>v;
arr[x-1][y-1]=v;
arr[y-1][x-1]=v;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j){
arr[i][j]=0;
}else if(arr[i][j]==0){
arr[i][j]=INF;
}
}
}
int temp=0;
for(int i=0;i<n;i++){
if(temp<f(i)){
temp=f(i);
}
}
int sum=0;
for(int i=1;i<=temp;i++){
sum+=(10+i);
}
cout<<sum;
return 0;
}
Post Views: 191