ЕГЭ · ЗАДАНИЕ 23
Графы и пути: новый формат 2027 · практика 13
В файле каждая строка содержит три числа u v w: есть направленное ребро из u в v весом w. Других рёбер нет. Найдите длину кратчайшего пути из вершины 1 в вершину 12.
Учебная модель Академии С для проверки приёма. Не выдаётся за задание реального экзамена.
Файлы к заданию
ege-23-checkpoint-5.txtИсточник задания
Сначала попробуй решить самостоятельно, затем открой разбор. Для автоматической проверки ответа включи JavaScript.
Показать решение по шагам
Разбор решения
Ответ: 52
Решение по шагам
- Все рёбра идут от меньшей вершины к большей. Значит, можно считать расстояния по возрастанию номеров. Обратных рёбер добавлять нельзя.
- Положим D[1]=0. Для каждого ребра u → v с весом w сравниваем нынешнее D[v] с D[u]+w и сохраняем меньшее.
- Кратчайший маршрут: 1 → 4 → 5 → 8 → 9 → 12. Его длина = 52.
| Вершина | Расстояние от 1 |
|---|---|
| 1 | 0 |
| 2 | 10 |
| 3 | 17 |
| 4 | 12 |
| 5 | 21 |
| 6 | 23 |
| 7 | 27 |
| 8 | 32 |
| 9 | 43 |
| 10 | 35 |
| 11 | 42 |
| 12 | 52 |
Проверка на Python
from math import inf
edges = [tuple(map(int, line.split())) for line in open("ege-23-checkpoint-5.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])