Олимпиад
Бодлогын өгүүлбэр
Улаанбаатар хотод програмчлалын олимпиад болж байна. Оролцогчид олимпиадад автобусаар ирж, буцдаг. Олимпиад дууссаны дараа нэг хүүхэд гэртээ аль болох эрт харихыг хүсэж байна. Харамсалтай нь олимпиад болж буй сургуулиас түүний гэрийн ойролцоох буудал хүртэл автобус бүр шууд явдаггүй. Мөн тэр буудал дээр зарим автобус зогсдоггүй (ер нь автобуснууд буудал бүр дээр зогсдоггүй). Хүүхэд автобуснаас буусан агшиндаа тэр буудал дээр зогсож буй өөр автобусанд сууж болно.
Автобусны буудлуудыг 1-ээс N хүртэлх тоогоор дугаарласан. 1-р буудал олимпиад болж буй сургуулийн дэргэд байрладаг бөгөөд хүүхэд 0 хугацааны агшинд тэр буудал дээр ирнэ гэж үзнэ. Хүүхдийн очих ёстой буудлын дугаар E.
Автобуснуудын хөдөлгөөний хуваарь өгөгдсөн бол хүүхэд гэртээ хүрч болох хамгийн бага хугацааг олох програм бич.
Эх сурвалж: ACMP №206 — Домой на электричках.
Оролтын формат
Эхний мөрөнд N ба E тоонууд өгөгдөнө. Хоёрдугаар мөрөнд автобусны рейсийн тоог илэрхийлэх M тоо өгөгдөнө.
Дараагийн M мөрөнд рейсийн мэдээлэл өгөгдөнө. Мөр бүр автобусны зогсох буудлын тоо Ki ба Ki ширхэг хос тоо нэг мөрөнд өгөгдөнө. Хос бүрийн эхний тоо нь буудлын дугаар, хоёр дахь нь автобус тухайн буудал дээр зогсох хугацаа юм. Нэг рейсийн буудлууд хугацааны өсөх дарааллаар эрэмбэлэгдсэн байна. Нэг рейсийн туршид автобус үргэлж нэг л чиглэлд явна.
Гаралтын формат
Хүүхэд өөрийн буудалд хүрч чадах хамгийн бага хугацааг илэрхийлэх тоог хэвлэнэ. Хэрэв рейсүүдээр гэрийн ойролцоох буудал хүрэх боломжгүй бол -1 хэвлэнэ.
Хязгаарлалт
- 2≤N≤100
- 2≤E≤N
- 0≤M≤100
- 2≤Ki≤N
- Хугацаа нь 0-ээс 109 хүртэлх бүхэл тоо.
Жишээ
5 3 4 2 1 5 2 10 2 2 10 4 15 4 5 0 4 17 3 20 2 35 3 1 2 3 40 4 45
20
Хүүхэд 3-р буудал руу очих ёстой. Тэр 4-р рейсээр 1-р буудлаас шууд явж болох ч 40 хугацаанд хүрнэ. Харин дамжин суувал илүү хурдан хүрнэ.
1-р буудлаас 5 хугацаанд 1-р рейсэд суугаад 2-р буудалд 10 хугацаанд хүрнэ. 2-р буудлаас яг 10 хугацаанд 2-р рейсэд суугаад 4-р буудалд 15 хугацаанд хүрнэ. 4-р буудал дээр 17 хүртэл хүлээж, 3-р рейсэд суугаад 3-р буудалд 20 хугацаанд хүрнэ.