Remote Training on Programming

После финала крупного международного турнира в городе Z группировка норвежских фанатов, возмущённая тем, что представлявшая Норвегию судейская бригада Томаса Эвребё не оказала решающего влияния на результат матча и не оказалась в центре внимания, решила оставить о себе «добрую» память жителям города.

Сделать это они решили довольно банальным, но проверенным способом — по дороге со стадиона в аэропорт разгромить городские улицы. Однако, во избежание проблем с местой полицией, подобную акцию необходимо тщательно спланировать.

Карта города Z представляет собой сеть улиц, соединяющих перекрестки. Движение по улицам двустороннее. Изучив карту и оценив длины городских улиц, лидеры «Ultras» приняли решение добраться в аэропорт кратчайшим по суммарной длине путем. Но для того, чтобы память о матче сохранилась в городском пейзаже надолго, было решено выбрать тот из кратчайших путей, который проходит через наибольшее число улиц. (Учитываются только те улицы, которые целиком лежат на пути).

Составление такого плана довольно трудоемко, и вряд ли кто-то из фанатов справился бы с этим, особенно учитывая то, что настоящий ультрас никогда не приходит на стадион трезвым. Поэтому за помощью было решено обратиться к Вам.