Masala #XWHBIND7NM
Transport
Dadorlandtiria mamlakatida ta shahar bor va ular 1 dan gacha raqamlangan.Shuningdek, mamlakatda 4 xil transport turi bor: avtobus, taksi, poyezd, samolyot.Sizga o’lchamlari 4 × N bo’lgan ikki o’lchamli a massiv berilgan. bu -transport yordamida -shahardan -shaharga borish uchun chipta narxi. Agar = −1 bo’lsa u holda bu transport bilan va -shaharlar orasida yurib bo’lmaydi. Bundan tashqari, har bir transport uchun oylik abonement mavjud. Agar siz qaysidir transportga abonement sotib olsangiz undan tekinga xohlaganingizcha foydalanishingiz mumkin. -transport abonementi dollar turadi. Vazifangiz 1-shahardan -shaharga borish uchun eng kamida qancha pul sarflash kerakligini topish. E’tibor bering, Dadorlandtiria mamlakatida barcha yo’llar bir tomonlik. Ya’ni i-shahardan -shaharga o’tish mumkin, biroq -shahardan -shaharga o’tib bo’lmaydi.
Birinchi qatorda sizga sonlari beriladi - yo’llar soni va abonement narxlari.
Keyingi 4ta qatorda tadan butun son, ikki o’lchamli massiv elementlari.
Chegaralar
•
• , barcha uchun
• , barcha va uchun
Subtasks
1. (11 ball)
2. (10 ball) Abonement sotib olmasdan ham optimal javob topish mumkin.
3. (20 ball) Faqat 1 ta transportga abonement sotib olish orqali optimal javob topish mumkin.
4. (21 ball) Ko’pi bilan 2ta transportga abonement sotib olish orqali optimal javob topish mumkin.
5. (29 ball) Faqatgina 1 - va/yoki 2 - turdagi transportlar orqali optimal javobni topish mumkin.
6. (9 ball) Qo’shimcha chegaralarsiz.
Yagona qatorda 1-shahardan -shaharga borish uchun minimal pul miqdori.
# | input.txt | output.txt |
---|---|---|
1 |
5 11 5 10 99 -1 5 4 -1 -1 4 -1 -1 -1 9 -1 8 -1 6 -1 10 10 10 10 10 |
19 |
Masalan, = 5, = [11, 5, 10, 99] bo’lsin. 2- va 3- transportlarga = 5 + 10 = 15 dollarga
abonement sotib olamiz. Shunda:
* 1-shahardan 2-shaharga bepul boramiz. (2-transport orqali).
* 2 shahardan 3-shaharga bepul boramiz. (3-transport orqali).
* 3-shahardan 4-shaharga 4 dollar evaziga boramiz. (1-transport orqali).
* 4-shahardan 5-shaharga bepul boramiz. (3-transport orqali).
* 5-shahardan 6 shaharga bepul boramiz. (2-transport orqali). Jami 15 + 0 + 0 + 4 + 0 + 0 = 19 dollar ishlatdik. Ko’rsatish mumkinki 19 minimal javob.