Problem type :
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
ในประเทศแห่งหนึ่ง เมืองจำนวน N เมือง ถูกกำหนดชื่อด้วยจำนวนเต็มตั้งแต่ 1 ถึง N ที่ไม่ซ้ำกันเลย เมืองทั้งหมดถูกเชื่อมกันด้วยถนนทั้งสิ้น N-1 เส้น ทำให้เมืองสองเมืองใด ๆ สามารถไปมาหาสู่กันได้ด้วยเส้นทาง เส้นทางหนึ่งเสมอ
คุณเป็นชาวบ้านคนหนึ่งที่อาศัยอยู่ที่เมืองหมายเลข 1 และคุณต้องการทราบว่าเมืองที่อยู่ไกลจากเมืองหมายเลข 1 ที่สุดนั้น ห่างจากเมืองหมายเลข 1 เท่าไร
ข้อมูลนำเข้า
บรรทัดแรกประกอบด้วยจำนวนนับ n แทนจำนวนเมืองทั้งหมด ( 1 < n < 100 001 )
บรรทัดถัดมา n-1 บรรทัดเป็นข้อมูลของถนนแต่ละเส้น โดยจะประกอบด้วยจำนวนเต็ม Xi Yi Zi แสดงว่าถนนเส้นที่ i เชื่อมระหว่างเมือง Xi และ Yi และมีความยาว Zi ( 1 < Xi,Yi < n , Xi != Yi , 1 < Zi < 3000 )
ข้อมูลส่งออก
บรรทัดเดียว ประกอบด้วยจำนวนเต็ม 1 จำนวน แสดงระยะทางระหว่างเมืองหมายเลข 1 กับเมืองที่อยู่ไกลเมืองหมายเลข 1 มากที่สุด
หมายเหตุ มีชุดทดสอบทั้งสิ้น 28 ชุดโดย
4 ชุดทดสอบ n = 11
3 ชุดทดสอบ n = 101
3 ชุดทดสอบ n = 10001
5 ชุดทดสอบ n = 30001
4 ชุดทดสอบ n = 50001
9 ชุดทดสอบ n = 100001
โจทย์โดย : สรวิทย์ สุริยกาญจน์ ( PS.int )
ที่มา : ศูนย์ สอวน. โรงเรียนมหิดลวิทยานุสรณ์
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 11 1 2 1427 1 3 741 1 4 1763 1 5 2491 1 6 1849 2 7 1219 3 8 1100 4 9 1071 3 10 1587 2 11 1418 | 2845 |
| 11 1 2 2445 2 3 1474 3 4 2493 4 5 1596 5 6 605 6 7 1531 7 8 1462 8 9 1389 9 10 1726 10 11 2112 | 16833 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้