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

Одоо оройн хоолны цаг бөгөөд үнээнүүд тус тусын бэлчээртэй гарчээ. Жоныг хонх дуугаргахад үнээнүүд саравч руугаа буцаж ирдэг. Чиний даалгавар бол аль үнээ саравчиндаа түрүүлж ирэхийг олох (оролтууд нэг үнээ түрүүлж ирэхээр өгөгдөх болно).

Саалийн цагуудын хооронд үнээнүүд өөр өөрийн бэлчээртэй гарсан байх бөгөөд үнээгүй талбар байж болно. Бэлчээрийн талбар бүр нэг буюу түүнээс олон талбар руу холбогдсон замтай. Зарим тохиолдолд 2 бэлчээрийн хооронд нэгээс олон зам байж болно. Нэг буюу түүнээс олон бэлчээрээс үнээний саравч руу холбогдсон зам бий. Тиймээс үнээ бүрт саравч хүрэх зам байгаа бөгөөд тэд бүгд саравчиндаа хүрэх хамгийн богино замыг мэддэг. Үнээ бүр дурын чиглэлд явах боломжтой бөгөөд бүгд ижил хурдаар алхдаг.

Бэлчээрүүд ‘a’-‘z’ болон ‘A’-‘Z’ гэж тэмдэглэгдсөн бөгөөд. Тухайн бэлчээрт байх үнээ нь ‘A’-‘Y’ гэсэн том үсгүүдээр тэмдэглэгдсэн. Жижиг үсгээр тэмдэглэгдсэн бэлчээрт үнээ байхгүй гэсэн үг. Үнээний саравч нь ‘Z’ үсгээр тэмдэглэгдсэн бөгөөд одоогоор нэг ч үнээ саравчинд байхгүй.

Програмын нэр: comehome

 Оролтын формат

Жишээ оролт(файл comehome.in)

5

A d 6

B d 3

C e 9

d Z 8

e Z 3

Гаралтын формат

Нэг мөрөнд хоосон зайгаар тусгаарлагдсан үсэг болон тоо байна. Үсэг нь түрүүлж ирсэн үнээний дугаар тоо нь тухайн үнээний туулсан зам.

Жишээ гаралт (файл comehome.out)

B 11

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