ЕГЭ · ЗАДАНИЕ 23
Графы и пути: новый формат 2027 · практика 14
В файле каждая строка содержит три числа u v w: есть направленное ребро из u в v весом w. Других рёбер нет. Найдите длину кратчайшего пути из вершины 1 в вершину 12.
Учебная модель Академии С для проверки приёма. Не выдаётся за задание реального экзамена.
Файлы к заданию
ege-23-checkpoint-6.txtИсточник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 37
Решение по шагам
- Все рёбра идут от меньшей вершины к большей. Значит, можно считать расстояния по возрастанию номеров. Обратных рёбер добавлять нельзя.
- Положим D[1]=0. Для каждого ребра u → v с весом w сравниваем нынешнее D[v] с D[u]+w и сохраняем меньшее.
- Кратчайший маршрут: 1 → 2 → 5 → 8 → 9 → 12. Его длина = 37.
| Вершина | Расстояние от 1 |
|---|---|
| 1 | 0 |
| 2 | 4 |
| 3 | 12 |
| 4 | 21 |
| 5 | 18 |
| 6 | 27 |
| 7 | 36 |
| 8 | 24 |
| 9 | 27 |
| 10 | 37 |
| 11 | 40 |
| 12 | 37 |
Проверка на Python
from math import inf
edges = [tuple(map(int, line.split())) for line in open("ege-23-checkpoint-6.txt")]
d = {v: inf for edge in edges for v in edge[:2]}
d[1] = 0
for u in sorted(d):
for a, b, w in edges:
if a == u: d[b] = min(d[b], d[u] + w)
print(d[12])