Задание 23 ЕГЭ по информатике

10971

Способ 1. Перебор всех путей (самый простой)

Так как граф небольшой, то можно пройти всеми возможными путями и выбрать минимальный используя рекурсивный DFS (обход графа в глубину).

# Объявляем список смежности
graph = {}

with open("23.txt") as f:
    for line in f:
        l, m, w = line.split()
        l = int(l)
        m = int(m)
        w = float(w)

        if l not in graph:
            graph[l] = []

        graph[a].append((m, w))


# Ищем все пути
def dfs(v, current_sum):
    global answer

    # Достигли конечной вершины
    if v == 100:
        answer = min(answer, current_sum)
        return

    # Перебираем все исходящие ребра
    for to, weight in graph.get(v, []):
        dfs(to, current_sum + weight)


answer = float("inf")
dfs(1, 0)
print(int(answer))

Ответ: 10971.

Способ 2. Алгоритм Дейкстры (классический подход)

Данный алгоритм работает для любых ориентированных графов и положительных весов.

import heapq

# Объявляем список смежности
graph = {}

with open("23.txt") as f:
    for line in f:
        l, m, w = line.split()

        l = int(l)
        m = int(m)
        w = float(w)

        graph.setdefault(l, []).append((m, w))

# Объявим словарь для хранения всех расстояний до вершин
dist = {}

# Объявим очередь с приоритетом: (расстояние, вершина)
queue = [(0, 1)]

# Расстояние до начальной вершины всегда нулевое
dist[1] = 0

# Пока в очереди есть вершины для обработки
while queue:
    # Берём вершину с самым маленьким расстоянием
    current_dist, v = heapq.heappop(queue)

    # Если нашли лучший путь раньше
    if current_dist > dist[v]:
        continue

    # Дошли до конечной вершины
    if v == 100:
        break
    
    # Перебираем все вершины, в которые можно попасть из v
    for to, weight in graph.get(v, []):
        # Рассчитываем новый возможный путь: путь до текущей вершины + вес нового ребра
        new_dist = current_dist + weight

        # Если вершина ещё не посещалась или нашли более короткий путь, обновляем расстояние
        if to not in dist or new_dist < dist[to]:
            # Запоминаем лучший найденный путь
            dist[to] = new_dist

            # Добавляем новую вершину в очередь
            # В следующий раз алгоритм обработает вершину с минимальным расстоянием
            heapq.heappush(
                queue,
                (new_dist, to)
            )

# Используем int(), так как требуется целая часть длины пути
print(int(dist[100]))

Ответ: 10971.

Способ 3. Топологическая сортировка + динамическое программирование (самый идеальный)

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

from collections import deque

# Объявляем список смежности графа
graph = {}

# Количество входящих рёбер для каждой вершины
indegree = {}

# Список всех вершин графа
vertices = set()

with open("23.txt") as f:
    for line in f:
        l, m, w = line.split()

        l = int(l)
        m = int(m)
        w = float(w)

        # Добавляем вершины
        vertices.add(l)
        vertices.add(m)

        # Добавляем ребро l -> m
        graph.setdefault(l, []).append((m, w))

        # Считаем количество входящих рёбер
        indegree[b] = indegree.get(m, 0) + 1
        indegree.setdefault(l, 0)

# Начинаем топологическую сортировку
queue = deque()

# В очередь добавляем вершины, в которые ничего не входит
for v in vertices:
    if indegree[v] == 0:
        queue.append(v)

order = []

while queue:
    v = queue.popleft()
    order.append(v)

    # Удаляем исходящие рёбра вершины
    for to, w in graph.get(v, []):

        indegree[to] -= 1

        # Если больше нет входящих рёбер, вершину можно обработать
        if indegree[to] == 0:
            queue.append(to)

# Начинаем поиск кратчайшего пути
INF = float("inf")

# dp[v] — минимальный вес пути из вершины 1 в вершину v
dp = {v: INF for v in vertices}

# Начальная вершина имеет путь длины 0
dp[1] = 0

# Идём по вершинам в правильном порядке
for v in order:
    # Проверяем все исходящие рёбра
    for to, w in graph.get(v, []):

        # Если через вершину v путь короче, обновляем расстояние
        if dp[v] + w < dp[to]:
            dp[to] = dp[v] + w

print(int(dp[100]))

Ответ: 10971.