1111 : เมืองหลวง (Capital)
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

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 22 ผู้เยี่ยมชมและ 0 สมาชิก (5 บอท)