ДАРХАНЫ 26-р ДУНД СУРГУУЛЬ / USACO /

Фермер Жон хамгийн амттай цөцгий хийх нууцыг олжээ. Энэ нь үнээний тэжээлд ёотон холих юм. Жон үнээнүүд ёотонг амтархан иднэ гэдгийг мэдэж байгаа бөгөөд ингэснээр сүү нь чихэрлэг болж, сүүгээр нь амтлаг цөцгий хийж илүү өндөр үнээр зарах юм. Мэдээж тэр үнээнүүдийнхээ нэмэлт тэжээлд мөнгө төлнө.

Жон бол тун ч овжин эр. Тэр үнээнүүдийг хонхны дуу сонсмогцоо заасан бэлчээр рүү явдаг болгож сургаж чадах бөгөөд үүнийгээ ч тэр сайн мэдэж байгаа. Тэр очихоор сургасан бэлчээртэй ёотон тавьж яг үд дунд хонх дуугаргах санаатай байгаа ингэснээр оройны саалин дээр үнээнүүд нь түүний хүссэн амттай сүүг өгөх юм.

Үнээнүүд хонх дуугараагүй л бол өөрийн бэлчээртээ л байдаг ( бэлчээрт нэг үнээ байх албагүй ). Бэлчээрүүдийн байрлал болон тэдгээрийн хооронд дахь замын урт өгөгдсөн бол фермер Жоныг хонх цохих үед бүх үнээнүүдийн явах замын нийлбэр хамгийн бага байхаар ёотон тавих бэлчээрийг ол. Жон бэлчээрүүдээ сайтар зохион байгуулалттайгаар холбосон тул ямар ч нөхцөлд бодлогонд шийд олдоно.

ПРОГРАМЫН НЭР: butter

ОРОЛТЫН ФОРМАТ

• 1-р мөр: Зайгаар тусгаарлагдсан 3 бүхэл тоо байна. Эдгээр нь үнээнүүдий тоо N, бэлчээрийн тоо P (2 <= P <= 800), замын тоо C (1 <= C <= 1,450). Үнээнүүд нь 1-ээс N хүртэл давхцалгүйгээр дугаарлагдсан. Бэлчээрүүд нь 1-ээс P хүртэл давхцалгүйгээр дугаарлагдсан.
•  2-оос N+1 мөр: Мөр бүрт нэг бүхэл тоо байна. Энэ нь үнээний бэлчээрийн дугаар. i дугаар үнээний бэлчээрийн дугаар i+1 мөрөнд байна.
•  N+2-ээс N+C+1 мөр: Мөр бүрт хоёр бэлчээр болон тэдгээрийг холбох замын уртыг илэрхийлэх зайгаар тусгаарлагдсан гурван бүхэл тоо байна. Замын аль ч талаас нь нөгөө тал руу нь явж болно. Аль ч хоёр бэлчээрийн хооронд нэгээс олон зам байхгүй. Эхний хоёр бүхэл тоо нь 1-ээс P-гийн хооронд. Гурав дахь тоо нь [1..255] завсар байна.

ЖИШЭЭ ОРОЛТ (файл butter.in)

3 4 5

2

3

4

1 2 1

1 3 5

2 3 7

2 4 3

3 4 5

ОРОЛТЫГ НАРИЙН ТАЙЛБАРЛАВАЛ:

Доорхи зурагт замуудыг геометрээр үзүүллээ.

               P2

 P1 @--1--@ C1

       \           |\

        \          | \

         5       7  3

          \        |     \

           \       |       \ C3

            C2   @---5---@

                    P3     P4

ГАРАЛТЫН ФОРМАТ

•  1-р мөр: Ёотонтой бэлчээрт хүрэхийн тулд үнээнүүд хамгийн багадаа ямар зам туулахыг илэрхийлэх нэг бүхэл тоо байна.

ЖИШЭЭ ГАРАЛТ(файл butter.out)

8

Гаралтыг тайлбарлавал:

Ёотонг 4 дүгээр бэлчээрт тавибал: 1-р үнээ 3 нэгж зам, 2-р үнээ 5 нэгж зам 3-р үнээ 0 нэгж зам нийт 8 нэгж зам туулна.

Орчуулсан Б.Даваабаяр