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