C. Синкропасотрон

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Хэсэг туршилтад зориулж бяцхан Петя-д синкропасотрон хэрэг болжээ. Тэрээр уг төхөөрөмжийг аль хэдийн олсон бөгөөд одоо зөвхөн түлшний хангамжийг тохируулах хэрэгтэй байв. Түлш $1$-ээс $n$ хүртэл дугаарлагдсан зангилааны цэгүүдийн систем уруу орж ирэх бөгөөд эдгээр зангилааны цэгүүд нь хоорондоо хоолойгоор холбогдсон байх юм. Хоолойнууд нь бага дугаартай зангилааны цэг болгоноос их дугаартай зангилааны цэг болгон уруу явсан байна. Мөн түлш нь зөвхөн бага дугаартай зангилааны цэгээс их дугаартай зангилааны цэг уруу урсах юм. Эхний зангилааны цэг уруу ямар ч хэмжээний түлш орж ирж болох бөгөөд хамгийн сүүлийн зангилааны цэг нь синкропасотрон-той шууд холбогдсон байна. Мөн хоолой бүр нь 3-н тоогоор илэрхийлэгдэнэ: уг хоолойгоор урсан явах ёстой хамгийн бага түлшний хэмжээ, уг хоолойгоор урсан явж болох хамгийн их түлшний хэмжээ болон уг хоолойн зардал гэсэн 3-н тоо байна. Хэрэв $c_{ij}$ нэгж хэмжээний түлш ($c_{ij} > 0$) $i$-р зангилааны цэгээс $j$-р зангилааны цэг уруу урсвал төлбөр нь $a_{ij} + c_{ij}^{2}$ ($a_{ij}$ нь уг хоолойн зардал байна) төгрөг байх бөгөөд хэрэв түлш хоолойгоор урсахгүй бол ямар ч зардал гарахгүй байна. Мөн хоолой бүрээр зөвхөн бүхэл тоон нэгж түлш урсаж болно.

Ямар нэгэн хоолойн багтаамжийн хамгийн бага болон хамгийн их түлшний талаарх шаардлагууд нь тухайн хоолойг хэрэглэж байгаа эсэхийг хамаарахгүйгээр үргэлж хэрэгжиж байх юм. Хэрэв тухайн хоолойгоор урсаж байгаа түлшний хэмжээ 0-ээс эрс их байвал та уг хоолойг хэрэглэж байгаа гэж үзнэ үү.

Петя уг хоолойнуудын системд хэт их ачаалал өгөхийг хүсэхгүй байгаа тул тэрээр эхний зангилааны цэг уруу орон синкропасотрон-д хүрч чадах хамгийн бага түлшний хэмжээг олохыг хүсжээ. Түүнчлэн тэрээр ивээн тэтгэгч нарыгаа ятгахыг хүсэж байгаа бөгөөд иймд тэрээр хоолой бүрээр урсах түлшинд төлөх нийт мөнгөний хэмжээ нь аль болох их байхыг хүсэж байв.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($2 ≤ n ≤ 6$) өгөгдөх ба энэ нь нийт зангилааны цэгүүдийн тоог илэрхийлнэ. Дараагийн $n(n - 1) / 2$ ширхэг мөрийн мөр болгонд хоолойнуудыг илэрхийлэх 5-н бүхэл тоо $s, f, l, h, a$-ууд өгөгдөнө. Эдгээр нь харгалзан тухайн хоолойн эхний зангилааны цэг, 2-дахь зангилааны цэг, тухайн хоолойгоор урсаж болох хамгийн бага болон хамгийн их түлшний хэмжээнүүд болон тухайн хоолойн зардлыг тус тус илэрхийлнэ ($1 ≤ s < f ≤ n, 0 ≤ l ≤ h ≤ 5, 0 ≤ a ≤ 6$). Ялгаатай дугааруудтай хос зангилааны цэг бүрийн хувьд тэдгээрийн хооронд орших яг нэг ширхэг хоолой оролтод өгөгдсөн байна.

Гаралт

Гаралтын эхний мөрөнд зайгаар тусгаарлагдсан 2 тоо хэвлэнэ: эдгээр нь синкропасотрон уруу урсан хүрч чадах хамгийн бага түлшний хэмжээ болон синкропасотрон-д ийм хэмжээний түлш хүрч очихын тулд төлөх ёстой мөнгөний боломжит хамгийн их утгыг илэрхийлнэ. Хэрэв синкропасотрон-д ямар ч хэмжээний түлш хүрч чадахгүй байвал "-1 -1" гэж хэвлэнэ үү.

Синкропасотрон-д хүрч очих түлшний хэмжээ нь заавал эерэг байх албагүй юм. Хэрэв хоолой бүрийн хувьд тухайн хоолойгоор урсаж болох хамгийн бага түлшний хэмжээ нь 0-тэй тэнцүү байвал синкропасотрон-д хүрч очих түлшний хэмжээ нь 0-тэй тэнцүү байж болно.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
2
1 2 1 2 3
Гаралт
1 4
Оролт
3
1 2 1 2 3
1 3 0 0 0
2 3 3 4 5
Гаралт
-1 -1
Оролт
4
1 2 0 2 1
2 3 0 2 1
1 3 0 2 6
1 4 0 0 1
2 4 0 0 0
3 4 2 3 0
Гаралт
2 15
Оролт
3
1 2 0 2 1
1 3 1 2 1
2 3 1 2 1
Гаралт
2 6

Тэмдэглэл

Эхний жишээнд бид 1-р зангилааны цэгээс 2-р зангилааны цэг уруу 1 эсвэл 2 нэгж түлш урсгаж болно. Хамгийн бага хэмжээ нь 1 бөгөөд үүний зардал нь $a_{12} + 1^{2} = 4$ байна.

2-дахь жишээнд та 1-р зангилааны цэгээс 2-р зангилааны цэг уруу хамгийн ихдээ 2 нэгж түлш урсгаж чадах бөгөөд та 2-р зангилааны цэгээс 3-р зангилааны цэг уруу хамгийн багадаа 3 нэгж түлш урсгах хэрэгтэй болох юм. Гэвч харамсалтай нь ингэх боломжгүй байна.

3-дахь жишээнд боломжит хамгийн бага хэмжээ нь 2 байна. Та нэгж түлш бүрийг 2 янзаар урсгаж болно. 1->2->3->4 эсвэл 1->3->4 гэсэн замаар урсгах юм. Хэрэв та эхний замыг 2 удаа ашиглавал нийт зардал нь $a_{12} + 2^{2} + a_{23} + 2^{2} + a_{34} + 2^{2}$=14 болно. Хэрэв та 2-дахь замыг 2 удаа ашиглавал нийт зардал нь $a_{13} + 2^{2} + a_{34} + 2^{2}$=14 болох юм. Хэрэв та зам тус бүрийг ашиглавал (нэг нэгж түлш нь хоолойнуудаар 1->2, 2->3, 1->3 гэсэн дарааллын дагуу урсах бөгөөд 2 нэгж түлш нь 2-уулаа 3->4 гэж урсан синкропасотрон-д хүрч очих юм) нийт зардал нь $a_{12} + 1^{2} + a_{23} + 1^{2} + a_{13} + 1^{2} + a_{34} + 2^{2}$=15 болох бөгөөд энэ нь төлөх ёстой мөнгөний боломжит хамгийн их хэмжээ байх юм.

Мөн 1-р зангилааны цэгээс 4-р зангилааны цэг уруу шууд байдлаар ямар ч түлш урсаагүй учраас уг хоолойн зардлыг хариултад нэмэхгүй болохыг анхаарна уу.

Сэтгэгдлүүдийг ачааллаж байна...