Разборы · ЕГЭ, задание 23

Задание 23 ЕГЭ по информатике: кратчайший путь во взвешенном графе

Что проверяет задание

В файле — рёбра ориентированного ациклического взвешенного графа: в каждой строке номера вершин L и M и вес ребра W из L в M. Нужно найти длину кратчайшего пути между двумя вершинами и записать её целую часть. Задание рассчитано на программу. 1 балл.

Что нужно знать

• Вершины пронумерованы не подряд, поэтому расстояния удобно хранить в словаре.
• Релаксация ребра L → M: если dist[L] + W < dist[M], обновляем dist[M].
• Алгоритм Беллмана — Форда: повторяем релаксацию всех рёбер столько раз, сколько рёбер в графе (достаточно числа вершин минус 1). Рёбер здесь не больше 200, так что это мгновенно.
• Числа в строке разделены любым числом пробелов и табуляций — line.split() без аргументов справится.

Как решать

1. Прочитайте рёбра в список кортежей (L, M, W), пропуская пустые строки.
2. Запишите dist = {1: 0} для начальной вершины.
3. Много раз пройдите по всем рёбрам с релаксацией.
4. Выведите целую часть расстояния до конечной вершины.

Пример из демоверсии 2027

Типовой пример из условия — граф на рисунке. Кратчайший путь из 1 в 100: 1 → 7 → 100, его длина 5,5 + 2,0 = 7,5, целая часть — 7.

Задание: найдите целую часть длины кратчайшего пути из вершины 1 в вершину 100 для графа из файла (не больше 200 рёбер, номера вершин до 1000).

edges = []
for line in open("23.txt"):
    p = line.split()
    if p:
        edges.append((int(p[0]), int(p[1]), float(p[2])))

dist = {1: 0.0}
for _ in range(len(edges)):
    for l, m, w in edges:
        if l in dist and dist[l] + w < dist.get(m, float("inf")):
            dist[m] = dist[l] + w
print(dist[100], int(dist[100]))

Для файла демоверсии ответ — 10971.

Можно решить и алгоритмом Дейкстры (веса положительные) или динамикой по вершинам в топологическом порядке, но при двухстах рёбрах простой перебор релаксаций проще всего написать без ошибок.

Типичные ошибки

• Считают граф неориентированным и добавляют рёбра в обе стороны.
• Округляют ответ вместо того, чтобы взять целую часть.
• Читают строки через split(" ") и спотыкаются о табуляции и двойные пробелы.
• Делают один проход релаксации — его недостаточно, если рёбра в файле перемешаны.

Потренироваться: задание 23 новые варианты с проверкой ответа