极北之雪

Grade 100 Open Time Tuesday, 2 June 2020, 12:50 PM
Discount 0.8 Time Discount Tuesday, 2 June 2020, 12:50 PM
Allow late Yes Close Time Tuesday, 2 June 2020, 12:50 PM
Input file two.in Output file two.out

【题目描述】极北之雪(two)POJ 1849 每到冬天,极北之地就被厚厚的积雪覆盖,这时,清洁公司的两个机器人就会从S村庄出发,清扫连接各村庄的道路上的积雪,已知任意两个村庄之间只有一条道路连通且所有村庄都可以直接或间接到达。 因为各村庄均有魔法阵,所以机器人在村庄里行驶不会消耗魔法力,但在各村庄连接的道路上,每行驶一米将消耗一个单位的魔法力(无论积雪是否已被清扫)。全部道路清扫完毕后,两个机器人停在它们最后清扫到的村庄,无需返回出发点也无需汇合,试计算最少消耗的魔法力是多少? 【输入格式】 第一行两个整数N(1≤N≤100000)和S(1≤S≤N),表示村庄数和出发村庄的编号,村庄编号从1开始。 随后N-1行,每行三个整数A,B,C,表示A村庄与B村庄连接道路的长度C(1≤C≤1000)。 【输出格式】 输出最少消耗的魔法力。 【输入样例】 5 2 1 2 1 2 3 2 3 4 2 4 5 1 【输出样例】 6