Файлы и большие данные · тема 7 из 8
Кратчайший путь: хранить лучший результат
Взвешенный граф · проект ЕГЭ 2027 №23
Одна идея — один пример
Вес ребра — стоимость перехода. Для положительных весов алгоритм Дейкстры выбирает ещё не обработанную вершину с минимальной известной стоимостью и улучшает соседей.
direct = 10
via = 3 + 4
print(min(direct, via))Теперь решаем самостоятельно
Учебный шаг: три вершины и три ребра. Прежде чем писать общий алгоритм, перечисли возможные простые маршруты вручную.
Вводятся положительные веса AB, BC, AC на трёх строках. Граф неориентированный, состоит только из A, B, C. Выведи длину кратчайшего пути из A в C.
Пример входных данных и результата
Ввод:
3 4 10
Вывод:
7
Черновик и файл программы
Черновик сохраняется в этом браузере. Ctrl/⌘ + S — сохранить.
Результаты проверки
Напиши решение и нажми «Проверить код». Данные каждого теста подаются автоматически.
Нужна подсказка?
Путь либо прямой AC, либо через B. Положительные циклы не улучшают длину.
На чём легко ошибиться
Этот частный способ не заменяет Дейкстру в графе с большим числом вершин.
Разобрать один из способов решения
Сначала попробуй написать код сам. Сравни алгоритм, затем закрой разбор и воспроизведи решение без подсказки.
ab = int(input())
bc = int(input())
ac = int(input())
print(min(ac, ab + bc))Тесты проверяют результат на учебных примерах, но не доказывают правильность для любого входа. Объясни каждую строку и предложи собственный тест.
Перед следующей темой
Назови входные данные, результат, основной шаг алгоритма и граничный случай. Если использовал разбор, напиши решение заново. Для свободных экспериментов открой Python онлайн.
Все темы этого курса
Программа подготовлена по темам банка «Академии С». Официальные документы: ФИПИ. Справочник языка: Python. Не все экзаменационные задачи нужно решать программой: например, работа в таблицах требует освоения табличного редактора.