Задача #4393

Обход графа

Уровень ЕГЭ

(Л. Шастин) В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вершин графа, W – вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе количество различных путей из вершины с номером 1001 в вершину с номером 2002. Существование хотя бы одного такого пути гарантируется.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. 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
При условии поиска количества различных путей из вершины с номером 1 в вершину с номером 100 для приведённого примера верным ответом будет 3.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла

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

Скачать 23_4393.txt

Новая

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

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

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

Ответ

50389

def deikstra(st, fn):
    c = [0] * 10_001
    d = [float('inf')] * 10_001
    c[st] = 1
    d[st] = 0
    determined = set()
    while fn not in determined:
        curr = min([v for v in set(range(1, 10_001)) - determined if c[v] > 0], key=lambda x: d[x])
        determined.add(curr)
        for nxt in g.get(curr, []):
            d[nxt] = min(d[nxt], d[curr] + 1)
            c[nxt] += c[curr]
    return c[fn]

g = {}
for l in open('23_4393.txt'):
    u, v, _ = l.split()
    g.setdefault(int(u), []).append(int(v))

print(deikstra(1001, 2002))

Номер