1082 : เกินความจำเป็น (overtree)
Problem type : Batch
Time limit : 1.5 second(s)
Memory limit : 32 megabyte(s)
Problem type : Batch
Time limit : 1.5 second(s)
Memory limit : 32 megabyte(s)
การเตรียมงานทุกอย่างเป็นอันเรียบร้อย เหลือเพียงแต่แขกผู้ทรงเกียรติทั้งหลายที่ยังไม่มีใครมาถึงคฤหาสน์แห่งนี้เลยซักคน มีสายโทรศัพท์จากคนขับรถทัวร์มาแจ้งว่า รถทัวร์ที่รับแขกทุกคนมางานเลี้ยงกำลังหลงทางอยู่ในป่าพิศวง!
เดิมที คนขับรถจะต้องมีแผนที่เส้นทางลัดในป่า ซึ่งมีลักษณะเป็นรูปกราฟต้นไม้ ที่ประกอบไปด้วยจุดพักนักท่องเที่ยว N จุดและถนนเชื่อมระหว่างจุดพักนักท่องเที่ยว N-1 สายซึ่งมีความยาวต่าง ๆ และเป็นถนนแบบ Two-way และเชื่อมจุดพักนักท่องเที่ยวถึงกันได้หมด
แต่ด้วยความสะเพร่า คนขับรถเจ้าปัญหาได้ลืมแผนที่เส้นทางลัดในป่าไว้ที่บ้าน นั่นทำให้เขาเหลือแต่แผนที่เส้นทางในป่าฉบับเจาะลึก ซึ่งระบุระยะทางระหว่างจุดพักนักท่องเที่ยวต่าง ๆ แทนที่จะระบุถนนที่เชื่อมระหว่างจุดพักนักท่องเที่ยว ข้อมูลระยะทางที่ระบุในแผนที่ดังกล่าวมีทั้งสิ้น M ข้อมูล แต่ละข้อมูล i จะบอกว่าระหว่างจุดพัก u_i กับ v_i มีระยะทางห่างกัน d_i โดยรับประกันว่า
งานของคุณ
จงเขียนโปรแกรมรับจำนวนจุดพักนักท่องเที่ยวและข้อมูลระยะทางระหว่างคู่ของจุดพักนักท่องเที่ยวหลายแห่ง แล้วหาว่ามีถนนเส้นใดอยู่ในแผนที่ทางลัดบ้าง
ข้อมูลนำเข้า
บรรทัดแรกมีจำนวนเต็มบวก N (2≤N≤100,000) แทนจำนวนจุดพักนักท่องเที่ยวทั้งหมดและจำนวนเต็ม M (N-1≤M≤1,000,000) แทนข้อมูลความยาวของระยะทางระหว่างคู่ของจุดพักนักท่องเที่ยว
อีก M บรรทัดถัดไป จะมีข้อมูลระยะทางระหว่างจุดพักนักท่องเที่ยวสองแห่งในแผนที่ฉบับเจาะลึก กล่าวคือในบรรทัดที่ i+1 ของข้อมูลนำเข้า โดยที่ 1≤i≤M จะระบุจำนวนเต็ม u_i,v_i,d_i ซึ่งหมายความว่าเส้นทางระหว่างจุดพักนักท่องเที่ยว u_i และ v_i บนกราฟต้นไม้นี้มีระยะทางเป็น d_i (1≤u_i,v_i≤N และ u_i≠v_i)
ข้อมูลส่งออก
มี N-1 บรรทัด บอกคู่ของถนนที่ปรากฏในแผนที่เส้นทางลัด บรรทัดละหนึ่งคู่ โดยสามารถแสดงคำตอบในลำดับใดก็ได้
โจทย์โดย: อาภาพงศ์ จันทร์ทอง
ที่มา: TOI.CPP:02-2009
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
เดิมที คนขับรถจะต้องมีแผนที่เส้นทางลัดในป่า ซึ่งมีลักษณะเป็นรูปกราฟต้นไม้ ที่ประกอบไปด้วยจุดพักนักท่องเที่ยว N จุดและถนนเชื่อมระหว่างจุดพักนักท่องเที่ยว N-1 สายซึ่งมีความยาวต่าง ๆ และเป็นถนนแบบ Two-way และเชื่อมจุดพักนักท่องเที่ยวถึงกันได้หมด
แต่ด้วยความสะเพร่า คนขับรถเจ้าปัญหาได้ลืมแผนที่เส้นทางลัดในป่าไว้ที่บ้าน นั่นทำให้เขาเหลือแต่แผนที่เส้นทางในป่าฉบับเจาะลึก ซึ่งระบุระยะทางระหว่างจุดพักนักท่องเที่ยวต่าง ๆ แทนที่จะระบุถนนที่เชื่อมระหว่างจุดพักนักท่องเที่ยว ข้อมูลระยะทางที่ระบุในแผนที่ดังกล่าวมีทั้งสิ้น M ข้อมูล แต่ละข้อมูล i จะบอกว่าระหว่างจุดพัก u_i กับ v_i มีระยะทางห่างกัน d_i โดยรับประกันว่า
- จะมีข้อมูลระยะทางระหว่างเมืองสองเมืองที่มีถนนเชื่อมกันโดยตรง ปรากฏเป็นหนึ่งข้อมูลหนึ่งใน M ข้อมูลนี้เสมอ
- ระยะทางของถนนระหว่างจุดพักนักท่องเที่ยวใดๆ จะไม่เกิน 10,000 เมตรเสมอ
- ไม่มีข้อมูลของระยะทางระหว่างคู่จุดพักใด ๆ ที่ปรากฏในข้อมูลนำเข้ามากกว่าหนึ่งครั้ง
งานของคุณ
จงเขียนโปรแกรมรับจำนวนจุดพักนักท่องเที่ยวและข้อมูลระยะทางระหว่างคู่ของจุดพักนักท่องเที่ยวหลายแห่ง แล้วหาว่ามีถนนเส้นใดอยู่ในแผนที่ทางลัดบ้าง
ข้อมูลนำเข้า
บรรทัดแรกมีจำนวนเต็มบวก N (2≤N≤100,000) แทนจำนวนจุดพักนักท่องเที่ยวทั้งหมดและจำนวนเต็ม M (N-1≤M≤1,000,000) แทนข้อมูลความยาวของระยะทางระหว่างคู่ของจุดพักนักท่องเที่ยว
อีก M บรรทัดถัดไป จะมีข้อมูลระยะทางระหว่างจุดพักนักท่องเที่ยวสองแห่งในแผนที่ฉบับเจาะลึก กล่าวคือในบรรทัดที่ i+1 ของข้อมูลนำเข้า โดยที่ 1≤i≤M จะระบุจำนวนเต็ม u_i,v_i,d_i ซึ่งหมายความว่าเส้นทางระหว่างจุดพักนักท่องเที่ยว u_i และ v_i บนกราฟต้นไม้นี้มีระยะทางเป็น d_i (1≤u_i,v_i≤N และ u_i≠v_i)
ข้อมูลส่งออก
มี N-1 บรรทัด บอกคู่ของถนนที่ปรากฏในแผนที่เส้นทางลัด บรรทัดละหนึ่งคู่ โดยสามารถแสดงคำตอบในลำดับใดก็ได้
โจทย์โดย: อาภาพงศ์ จันทร์ทอง
ที่มา: TOI.CPP:02-2009
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 5 6 1 2 2 2 3 3 1 4 6 2 4 4 3 5 9 4 5 2 | 1 2 2 3 2 4 4 5 |
| 6 5 1 2 1 2 3 2 3 4 5 4 5 11 5 6 4 | 1 2 2 3 3 4 4 5 5 6 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 2 ผู้เยี่ยมชมและ 0 สมาชิก (1 บอท)