Задача B. Поиск кратчайшего пути ≡
| Автор: | Баранов А.А., Ян Т.В. | Ограничение времени: | 1 сек | |
| Максимальный балл: | 100 | Ограничение памяти: | 256 Мб |
Условие
Пусть имеется граф из 26 вершин, промаркированных заглавными буквами латинского алфавита от A до Z (см. рисунок).
Каждому ребру такого графа приписан некоторый целочисленный вес, обозначающий время, за которое его можно пройти.
Требуется определить кратчайший маршрут, ведущий из вершины A в вершину Z
и проходящий через как можно большее число вершин.
Формат выходных данных
В качестве ответа требуется вывести строку, составленную из маркеров вершин,
через которые проходит такой маршрут, в порядке их обхода (например, AZ).
Полученный ответ введите в текстовое поле: