🆘Разбираем НОВЫЙ №23 из ДЕМКИ ЕГЭ-2027

В условии нам дают ориентированный взвешенный граф.
Каждая строка файла содержит три числа:

L M W

Это означает, что есть ребро

L → M с весом W.

Например:

73 100 7990.0

означает переход из вершины 73 в вершину 100 с весом 7990.

Наша задача - найти кратчайший путь из вершины 1 в вершину 100, то есть такой путь, у которого сумма весов всех рёбер минимальна.
В реальном файле 200 строк, поэтому руками перебирать маршруты уже не хочется. Решаем программой.

Сначала считываем все рёбра:

a, b, w = line.split()

split() здесь особенно удобен: он сам справляется с любым количеством пробелов и табуляций между числами.

Все рёбра сохраняем в список edges.
Дальше создаём список:

d = [float("inf")] * 1001

d[i] будет хранить минимальную известную длину пути из вершины 1 в вершину i.

Изначально мы знаем только одно:

d[1] = 0 - до самой первой вершины расстояние равно нулю.

После этого несколько раз проходим по всем рёбрам.
Для каждого ребра

a → b

проверяем:

if d[a] + w < d[b]:

То есть: если путь до b через вершину a оказался короче того, который мы знали раньше, обновляем значение:

d[b] = d[a] + w

🩷Почему проходов несколько?
Потому что рёбра в файле расположены в случайном порядке. Может случиться, что нужное ребро встретилось раньше, чем мы вообще узнали, как добраться до его начала. На следующем проходе эта информация уже появится.

Если за целый проход ничего не изменилось:

if not changed:
break

значит, более коротких путей мы уже не найдём.
В конце:

print(int(d[100]))

берём расстояние до вершины 100 и записываем его целую часть - именно это требует условие.

➡️Главная идея задачи:

d[b] = min(d[b], d[a] + w)

Если через текущую вершину можно добраться дешевле - запоминаем новый минимум.

На вид условие огромное, а в итоге вся логика держится буквально на одной проверке 🙂