Кружок программирования готовит программу для школьного турнира. Результаты участников хранятся в текстовом файле results.txt, по одной строке на участника в формате «Фамилия;класс;баллы», например «Ахметов;9;72». Строка делится на части по символу «;». Функция len возвращает количество всех символов строки, включая символ «;». В файле шесть записей: «Ахметов;9;72», «Беков;10;85», «Ким;9;85», «Сулейменова;11;64», «Дюсенов;10;90», «Омарова;9;58». Для упорядочивания участников используется сортировка пузырьком по убыванию баллов: проход выполняется один раз от начала списка до конца, соседние элементы сравниваются по очереди, и если левый меньше правого, их меняют местами. Для контрольного числа результата применяется рекурсивная функция sum_digits(n): если n < 10, результат равен n; иначе результат равен (n mod 10) + sum_digits(n div 10), где mod — остаток от деления, а div — целая часть от деления. Файл можно открывать в разных режимах: «r» — только чтение, «w» — запись, при которой прежнее содержимое файла удаляется, «a» — запись в конец файла. После турнира участники едут из пункта A в пункт E. Пункты A, B, C, D, E соединены двусторонними дорогами: A–B 4 км, A–C 2 км, B–C 1 км, B–D 5 км, C–D 8 км, D–E 3 км. Эту сеть дорог программа хранит как граф: пункты — вершины, дороги — рёбра с длинами.
Какова длина кратчайшего маршрута из пункта A в пункт E по графу дорог из текста?
Показать ответ и разборСкрыть ответ и разбор
Верный ответ
- D11 км
Разбор
Сравним маршруты из A в E. A–C–B–D–E: 2 + 1 + 5 + 3 = 11 км. A–B–D–E: 4 + 5 + 3 = 12 км. A–C–D–E: 2 + 8 + 3 = 13 км. A–B–C–D–E: 4 + 1 + 8 + 3 = 16 км. Кратчайший маршрут равен 11 км. В пункт E можно попасть только через D, поэтому маршрут заканчивается участком D–E.