Сніг не проблема

У Юлліхському інженерно-технологічному інституті (YETI), розташованому на півночі Сноубловії, є дві проблеми: сніг і гроші. Зокрема, у них занадто багато першого і недостатньо другого. Кожної зими (а також восени і навесні, якщо на те пішло) кампус вкривається снігом, а тротуари, що з'єднують будівлі кампусу, стають непрохідними. Щоб продовжити роботу, YETI необхідно розчистити від снігу тротуари, що з'єднують будівлі кампусу. Оскільки бюджет є проблемою, ці тротуари представляють собою мінімальний набір, що дозволяє створити шлях між будь-якими двома будівлями.

На гроші, зекономлені за рахунок відмови від будівництва нових тротуарів, YETI купила два снігоочисники. Щоб з їх допомогою розчистити сніг, два співробітники виносять два снігоочисники з будівель (або будівлі), в яких вони зберігаються, і штовхають їх по тротуарах, розчищаючи сніг. Кожен тротуар необхідно перетнути хоча б один раз. Кожен снігоочисник після завершення роботи зберігається в будівлі, поруч з якою він знаходиться в даний момент (а під час наступного снігопаду снігоочисники будуть рухатися у зворотному напрямку — і так протягом одинадцяти місяців снігового сезону).

Технічна бригада YETI хоче вибрати будівлі для зберігання снігоочисників і спроектувати маршрути, за якими вони будуть переміщатися, таким чином, щоб звести до мінімуму загальну відстань, яку дві машини пройдуть на морозі (щоб захистити як цінне обладнання, так і співробітників від замерзання). Зверніть увагу, що маршрути можуть включати рух по вже розчищених тротуарах, як показано на рисунку J.1, де показано оптимальне рішення для схеми тротуару з прикладу вхідних даних 1.

YETI попросили свій відділ комп'ютерних наук розібратися в цьому, але він був знищений під час Великої хуртовини 2006 року, тому вони звернулися до Вас за допомогою.