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

import heapq
from collections import defaultdict

graph = defaultdict(list)  # вершина -> [(куда ведёт ребро, вес)]
with open('23.txt') as f:
    for line in f:
        parts = line.split()  # любое число пробелов и табуляций
        if len(parts) == 3:
            l, m, w = int(parts[0]), int(parts[1]), float(parts[2])
            graph[l].append((m, w))

# алгоритм Дейкстры: все веса положительны
dist = {1: 0.0}
heap = [(0.0, 1)]
while heap:
    d, v = heapq.heappop(heap)
    if d > dist[v]:
        continue  # устаревшая запись: до v уже нашли путь короче
    for u, w in graph[v]:
        if d + w < dist.get(u, float('inf')):
            dist[u] = d + w
            heapq.heappush(heap, (d + w, u))

print(int(dist[512]))  # целая часть, не round()

from functools import lru_cache
from collections import defaultdict

incoming = defaultdict(list)  # вершина -> из каких вершин в неё ведут рёбра
with open('23.txt') as f:
    for line in f:
        parts = line.split()
        if len(parts) == 3:
            incoming[int(parts[1])].append(int(parts[0]))


@lru_cache(maxsize=None)
def ways(v):
    # путей из 1 в v столько, сколько их во все вершины, откуда есть ребро в v
    if v == 1:
        return 1
    return sum(ways(u) for u in incoming[v])


print(ways(100))

from collections import defaultdict, deque

graph = defaultdict(list)
indeg = defaultdict(int)  # сколько рёбер входит в вершину
nodes = set()
with open('23.txt') as f:
    for line in f:
        parts = line.split()
        if len(parts) == 3:
            l, m, w = int(parts[0]), int(parts[1]), float(parts[2])
            graph[l].append((m, w))
            indeg[m] += 1
            nodes |= {l, m}

# топологический порядок (алгоритм Кана): каждое ребро ведёт «вперёд»
queue = deque(v for v in nodes if indeg[v] == 0)
order = []
while queue:
    v = queue.popleft()
    order.append(v)
    for u, w in graph[v]:
        indeg[u] -= 1
        if indeg[u] == 0:
            queue.append(u)


def shortest(start):
    # расстояния от start за один проход в топологическом порядке
    dist = {v: float('inf') for v in nodes}
    dist[start] = 0.0
    for v in order:
        for u, w in graph[v]:
            dist[u] = min(dist[u], dist[v] + w)
    return dist


# путь через 105 = кратчайший 42 → 105 + кратчайший 105 → 100
print(int(shortest(42)[105] + shortest(105)[100]))