Задача #4432

Обход графа

Уровень ЕГЭ

(Л. Шастин) В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вершин графа, W – вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1207 в вершину с номером 7613, содержащего не более K = 20 рёбер. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. L ≤ 10000, M ≤ 10000; W ≤ 100. Количество строк в файле не превосходит 100 000. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле для графа на рисунке.

100 12 1.0
6 7 7.0
6 1 1.0
1 7 5.5
7 100 2.0
4 100 8.0
1 100 12.0
1 4 2.5
При условии поиска длины кратчайшего пути из вершины с номером 6 в вершину с номером 12, содержащего не более K = 3 рёбер, для приведённого примера верным ответом будет 10.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла

Файлы к задаче

Скачать 23_4432.txt

Новая

Введите ответ

Войдите, чтобы история ответов и статистика сохранялись.

Решение Нажми, чтобы открыть Нажми, чтобы скрыть

Ответ

222

def bellman_ford(st, fn, K=20):
    d = [float('inf')] * 10_001
    d[st] = 0
    for i in range(K):
        new_d = d[:]
        for u in g:
            if d[u] < float('inf'):
                for v, w in g[u]:
                    new_d[v] = min(new_d[v], d[u] + w)
        d = new_d
    return d[fn] / 100

g = {}
for l in open('23_4432.txt'):
    u, v, w = l.split()
    g.setdefault(int(u), []).append((int(v), float(w) * 100))

print(int(bellman_ford(1207, 7613)))

Номер