Е23.1 целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100

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

Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1 в вершину с номером 100.
Существование хотя бы одного такого пути гарантируется.
Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд.
L ≤ 1000, M ≤ 1000; W ≤ 10 000.
Количество строк в файле не превосходит 200.
Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

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

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

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

Для приведённого примера верным ответом будет 7.

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

TXT

Ответ:

Демонстрационный вариант ЕГЭ 2027 по информатике – задание №23

Для решения задачи удобно использовать алгоритм Дейкстры.
Он позволяет найти кратчайшее расстояние от одной вершины графа до всех остальных.
В нашей задаче нужно найти минимальное расстояние от вершины 1
до вершины 100.

from heapq import *

f = open('23.txt')

g = {}

for line in f:
    a, b, w = line.split()
    a = int(a)
    b = int(b)
    w = float(w)

    if a not in g:
        g[a] = []

    g[a].append((b, w))

d = {1: 0}
q = [(0, 1)]

while q:
    dist, v = heappop(q)

    if dist != d[v]:
        continue

    for to, w in g.get(v, []):
        nd = dist + w

        if to not in d or nd < d[to]:
            d[to] = nd
            heappush(q, (nd, to))

print(int(d[100]))

from heapq import *

f = open('23.txt')

g = {}

for line in f:

a, b, w = line.split()

a = int(a)

b = int(b)

w = float(w)

if a not in g:

g[a] = []

g[a].append((b, w))

d = {1: 0}

q = [(0, 1)]

while q:

dist, v = heappop(q)

if dist != d[v]:

continue

for to, w in g.get(v, []):

nd = dist + w

if to not in d or nd < d[to]:

d[to] = nd

heappush(q, (nd, to))

print(int(d[100]))

Разбор программы

Сначала подключаем функции для работы с очередью с приоритетом:

from heapq import *

1	from heapq import *

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

Открываем файл:

f = open('23.txt')

1	f = open('23.txt')

Создаём словарь g, в котором будем хранить граф:

g = {}

g = {}

Каждая строка файла содержит три значения:
номер начальной вершины, номер конечной вершины и вес ребра.

for line in f:
    a, b, w = line.split()

1 2	for line in f: a, b, w = line.split()

Например, строка

1 7 5.5

1 7 5.5

означает, что существует ребро

1 → 7

1 → 7

с весом 5.5.

Номера вершин преобразуем в целые числа,
а вес ребра — в вещественное число:

a = int(a)
b = int(b)
w = float(w)

a = int(a)

b = int(b)

w = float(w)

Если вершины a ещё нет в словаре, создаём для неё пустой список:

if a not in g:
    g[a] = []

1 2	if a not in g: g[a] = []

После этого добавляем в список вершину, в которую ведёт ребро,
и его вес:

g[a].append((b, w))

1	g[a].append((b, w))

Например, если в файле есть строки

1 7 5.5
1 4 2.5
1 100 12.0

1 7 5.5

1 4 2.5

1 100 12.0

то в словаре получится:

g[1] = [(7, 5.5), (4, 2.5), (100, 12.0)]

1	g[1] = [(7, 5.5), (4, 2.5), (100, 12.0)]

Массив расстояний

Создаём словарь d.
В нём будем хранить минимальное найденное расстояние
от вершины 1 до каждой вершины.

d = {1: 0}

1	d = {1: 0}

Расстояние от вершины 1 до самой себя равно 0.

Также создаём очередь:

q = [(0, 1)]

1	q = [(0, 1)]

Пара (0, 1) означает:
расстояние до вершины 1 равно 0.

Алгоритм Дейкстры

Пока очередь не пуста, извлекаем из неё элемент
с минимальным расстоянием:

while q:
    dist, v = heappop(q)

1 2	while q: dist, v = heappop(q)

Здесь:

dist — расстояние от вершины 1 до текущей вершины;
v — номер текущей вершины.

В очередь одна и та же вершина может попасть несколько раз.
Если найденное ранее расстояние уже меньше, старую запись пропускаем:

if dist != d[v]:
    continue

1 2	if dist != d[v]: continue

Теперь перебираем все рёбра, выходящие из вершины v:

for to, w in g.get(v, []):

1	for to, w in g.get(v, []):

Здесь:

to — вершина, в которую ведёт ребро;
w — вес этого ребра.

Метод

g.get(v, [])

1	g.get(v, [])

возвращает список всех рёбер, выходящих из вершины v.
Если из вершины нет исходящих рёбер, возвращается пустой список.

Вычисляем новое расстояние:

nd = dist + w

1	nd = dist + w

То есть к уже найденному расстоянию до вершины v
добавляем вес следующего ребра.

Далее проверяем:

if to not in d or nd < d[to]:

1	if to not in d or nd < d[to]:

Условие выполняется в двух случаях:

мы ещё ни разу не находили путь до вершины to;
новый путь оказался короче уже найденного.

Если найден более короткий путь, сохраняем новое расстояние:

d[to] = nd

1	d[to] = nd

и добавляем эту вершину в очередь:

heappush(q, (nd, to))

1	heappush(q, (nd, to))

Пример работы

Пусть имеются такие пути:

1 → 100 = 12

1 → 4 → 100 = 2.5 + 8 = 10.5

1 → 7 → 100 = 5.5 + 2 = 7.5

1 → 100 = 12

1 → 4 → 100 = 2.5 + 8 = 10.5

1 → 7 → 100 = 5.5 + 2 = 7.5

Сначала программа может найти прямой путь:

d[100] = 12

1	d[100] = 12

Затем найдётся более короткий путь через вершину 4:

d[100] = 10.5

1	d[100] = 10.5

После этого найдётся ещё более короткий путь через вершину 7:

d[100] = 7.5

1	d[100] = 7.5

Таким образом, кратчайший путь имеет длину 7.5.

Получение ответа

По условию требуется записать не само вещественное число,
а его целую часть.
Поэтому используем функцию int():

print(int(d[100]))

1	print(int(d[100]))

Для значения

7.5

7.5

получим:

7

Следовательно, для приведённого в условии примера ответ:
7.

Ответ: 10971