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