解题思路:
注意事项:
参考代码:
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static int n;
static List<Node>[] g;//定义一个存放了node节点的邻接表 比起领接矩阵更加节省空间
static long max = -10000000;
static int pnt = 1;//记录端点
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();//城市数
g = new List[n + 1];
for (int i = 1; i <= n; i++) {
g[i] = new ArrayList<Main.Node>();//初始化邻接表的每一个list
}
//规定了只有n - 1条路径
for (int i = 0; i < n - 1; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
g[a].add(new Node(b,c));//在编号为a的链表上添加所能到达的编号以及距离所组成的节点
g[b].add(new Node(a,c));//对称性
}
//以1为根 找到端点
//先从任意一点P出发,找离它最远的点Q,再从点Q出发,找离它最远的点W,W到Q的距离就是是的直径
dfs(2, 2, 0);
dfs(pnt, pnt, 0);
System.out.println(dis2Money(max));
}
//from记录了从哪个点来
public static void dfs(int from,int num,long dis) {
boolean ifLeaf = true;//先假设他就是叶子节点
List<Node> neighbours = g[num];//num节点的邻居
for (int i = 0; i < neighbours.size(); i++) {
Node neighbour = neighbours.get(i);//其中一个邻居
if(neighbour.num == from)continue;
//走到这说明除了父节点还有邻居
ifLeaf = false;
dfs(num, neighbour.num, dis + neighbour.dis);
}
if (ifLeaf && dis > max) {//是叶子节点
max = dis;
pnt = num;
}
}
//推算过程 公差为d的等差数列n项和为 首项a1 加 尾项 (a1 + a1 + (n - 1) * d ) * n / 2
public static long dis2Money(long dis) {
return 11 * dis + dis * (dis - 1) / 2;
}
static class Node{
int num;
long dis;
public Node(int num, long dis) {
super();
this.num = num;
this.dis = dis;
}
}
}
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:611 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:782 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:593 |
用筛法求之N内的素数。 (C语言代码)浏览:685 |
DNA (C语言代码)浏览:440 |
C语言训练-亲密数 (C语言描述,反正怎么都能对)浏览:2256 |
陈教主的三角形 (C语言代码)浏览:1196 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:548 |
字符逆序 (C语言代码)浏览:541 |
A+B for Input-Output Practice (III) (C语言代码)浏览:455 |