Теоретические основы информатики · 1 балл

Графы: пути

Кратчайший путь и количество путей

Найти кратчайший путь или количество различных путей в ориентированном графе.

Теория целое число новая тема 2027

2027

В 2027 тема задания изменена: теперь алгоритмы на графах. В 2026 задание проверяло анализ хода исполнения алгоритма.

Что проверяет

Графы: виды, оптимальный путь, количество путей в ориентированном ациклическом графе.

Основание: проект спецификации и кодификатора КИМ 2027. Открыть документы

Теория

Что нужно знать

Задание 23 в 2027 году проверяет работу с графами: нужно найти оптимальный маршрут или посчитать количество путей в ориентированном ациклическом графе. Это 1 первичный балл, но формулировки разнообразны: от простой схемы со стрелками до файла со списком рёбер.

Минимум для задания 23

читать ориентированный граф и его таблицу смежности
строить топологический порядок вершин
считать количество путей динамикой
учитывать обязательные и запрещённые вершины
находить кратчайший путь алгоритмом Дейкстры
читать граф из таблицы и из файла
восстанавливать маршрут и проверять ответ

Вершины, рёбра и направление

Граф состоит из вершин (городов, пунктов) и рёбер (дорог). В задании 23 почти всегда граф ориентированный: по каждой дороге можно двигаться только по стрелке.

Вершина — пункт, ребро — дорога между двумя пунктами.
Ориентированное ребро (дуга) задаёт движение только в одну сторону.
Взвешенный граф — у каждого ребра есть длина или вес.
Степень вершины — число связанных с ней рёбер; в ориентированном графе отдельно считают входы и выходы.
Путь из A в B — последовательность вершин, где каждая следующая соединена с предыдущей ребром в нужном направлении.

Путь, маршрут и цикл

В формулировках встречаются «путь», «маршрут» и «различных путей». В ЕГЭ путь не повторяет вершины, а маршрут может; в задании 23 обычно считают пути в ациклическом графе.

Простой путь не повторяет вершины.
Цикл — путь, который возвращается в уже пройденную вершину.
В графе с циклом путей между вершинами может быть бесконечно много.
В задании 23 граф ациклический, поэтому число путей конечно.
Разные пути различаются хотя бы одной вершиной или ребром.

Ориентированный ациклический граф

Ациклический ориентированный граф (DAG) — граф без циклов. В нём можно упорядочить вершины так, что каждое ребро ведёт от более ранней вершины к более поздней.

Топологический порядок — порядок вершин, при котором все рёбра идут слева направо.
В DAG всегда есть хотя бы одна вершина без входящих рёбер — с неё начинают.
Если обработать вершину раньше её предка, часть путей потеряется.
Топологический порядок строят алгоритмом Кана или обходом в глубину.
На небольших схемах порядок часто виден по стрелкам.

Динамика для количества путей

Главная формула задания: число путей в вершину равно сумме чисел путей во все вершины, из которых в неё ведёт ребро. Стартовой вершине ставим 1.

Обнулите все dp, кроме стартовой вершины.
Обрабатывайте вершины в топологическом порядке.
Для каждого ребра u → v прибавляйте dp[u] к dp[v].
В финишной вершине получится ответ.
Если нужно перечислить пути, а не только посчитать, используйте DFS.

dp[start] = 1dp[v] = Σ dp[u] для всех рёбер u → vответ = dp[finish]

Обязательные и запрещённые вершины

Фразы «проходящих через X» и «не проходящих через X» меняют граф, но не формулу динамики.

Через X: путь распадается на участки A → X и X → B, количества перемножаются.
Несколько обязательных вершин: перемножайте участки в порядке их прохождения.
Если порядок не указан, рассмотрите все допустимые порядки и сложите варианты.
Запрещённая вершина удаляется вместе со всеми входящими и исходящими рёбрами.
«Через X, но не через Y»: сначала удалите Y, затем считайте пути через X.
«Хотя бы через одну из вершин X или Y»: сложите пути через X и через Y и вычтите пути через обе.

Кратчайший путь

Если у рёбер есть длины и нужно найти минимальную сумму, используйте алгоритм Дейкстры. В ациклическом графе ту же задачу можно решить динамикой по топологическому порядку.

Дейкстра работает при неотрицательных весах.
Начните с dist[start] = 0, остальные расстояния — бесконечность.
Выбирайте непосещённую вершину с минимальным расстоянием и обновляйте соседей.
Для невзвешенного графа достаточно BFS: она даёт минимальное число рёбер.
Для DAG: dist[v] = min(dist[u] + w(u, v)) по всем входящим рёбрам.
Чтобы восстановить маршрут, запоминайте предыдущую вершину.

Граф в таблице, списке и файле

В заданиях граф задают тремя способами: рисунком со стрелками, таблицей длин или файлом со списком рёбер. Во всех случаях сначала постройте список смежности.

Таблица длин: на пересечении строки и столбца — вес ребра; пустая клетка означает отсутствие ребра.
Если таблица симметрична, граф неориентированный; для задания 23 проверьте стрелки.
Список рёбер: каждая строка L M W означает ребро из L в M с весом W.
Номера вершин в файле могут идти не подряд — используйте словарь, а не массив.
Пробелы и табуляции в файле могут быть любыми; используйте split().

Ответ и самопроверка

Ответ в задании 23 — целое число или строка из букв. Проверяйте его независимым способом: перебором, оценкой или повторным счётом.

Количество путей — целое неотрицательное число; 0 тоже возможен.
Длину пути записывайте целым числом; если веса вещественные, берите целую часть, как сказано в условии.
Маршрут записывайте подряд, без пробелов, если это требуется.
Проверьте старт и финиш: иногда они меняются местами.
Сравните ответ с числом путей, полученным перебором на маленьком графе.
Если ответ больше числа всех возможных маршрутов, ищите ошибку в направлении рёбер.

Разбор примера

Учебный пример: сколько путей из А в К

На схеме — ориентированный граф без циклов. Сосчитаем пути динамикой и проверим перебором.

Порядок обработки вершин и число путей из А
Вершина	А	Б	Г	В	Д	Е	К
dp	1	1	1	2	1	1	6

Топологический порядок: А, Б, Г, В, Д, Е, К. Важно: Г должно идти раньше В, иначе пути через Г → В потеряются.
dp[А] = 1 — это пустой путь из старта в старт.
dp[Б] = dp[А] = 1, dp[Г] = dp[А] = 1.
dp[В] = dp[Б] + dp[Г] = 2, dp[Д] = dp[Б] = 1, dp[Е] = dp[Г] = 1.
dp[К] = dp[Б] + dp[В] + dp[Г] + dp[Д] + dp[Е] = 1 + 2 + 1 + 1 + 1 = 6.

Ответ6 путей: А–Б–Д–К, А–Б–В–К, А–Б–К, А–Г–В–К, А–Г–К, А–Г–Е–К.

Способы решения

Выберите метод под формулировку

Методы собраны по решениям задания 23 из базы Kompege. Начните с того, что именно нужно найти в условии.

когда нужно только количество путей

Динамика по вершинам

Когда использовать: В условии спрашивают, сколько существует различных путей из A в B, и граф ациклический.

Выпишите список смежности: для каждой вершины — куда ведут её рёбра.
Постройте топологический порядок вершин.
Заведите dp: dp[start] = 1, остальные 0.
Идите по вершинам в топологическом порядке и прибавляйте dp[v] к каждому соседу.
Ответ — dp[finish].

Пример

Для графа из теории порядок А, Б, Г, В, Д, Е, К даёт dp[К] = 6. Если обработать В раньше Г, получится 5: путь А–Г–В–К потеряется.

graph = {
    'А': ['Б', 'Г'],
    'Б': ['Д', 'В', 'К'],
    'Г': ['В', 'К', 'Е'],
    'В': ['К'],
    'Д': ['К'],
    'Е': ['К'],
    'К': [],
}
order = ['А', 'Б', 'Г', 'В', 'Д', 'Е', 'К']
dp = {v: 0 for v in graph}
dp['А'] = 1
for v in order:
    for u in graph[v]:
        dp[u] += dp[v]
print(dp['К'])  # 6

Ответ6.

По мотивам задач № 21834 и № 57 (база Kompege).

когда в условии «проходящих через X»

Обязательная вершина: умножаем участки

Когда использовать: Нужно посчитать пути из A в B, которые обязательно проходят через вершину X.

Убедитесь, что X достижима из A и из неё достижима B.
Посчитайте число путей A → X.
Посчитайте число путей X → B.
Перемножьте результаты: каждый путь до X можно продолжить любым путём после X.
Если обязательных вершин несколько, перемножьте все участки в порядке прохождения.

Пример

Граф: A→B, A→C, B→D, B→E, C→D, C→E, D→F, D→E, E→F, E→G, F→G, G→H. Путей A→E — 4 (A–B–D–E, A–B–E, A–C–D–E, A–C–E), путей E→H — 2 (E–F–G–H, E–G–H). Через E проходит 4 × 2 = 8 путей.

Ответ8.

По мотивам задач № 21835, № 12 и № 214.

когда в условии «не проходящих через X»

Запрещённая вершина: удаляем её

Когда использовать: Нужно исключить все пути, которые заходят в вершину X.

Удалите X из списка смежности.
Удалите все рёбра, которые входят в X или выходят из неё.
Посчитайте пути в оставшемся графе обычной динамикой.
Не вычитайте пути через X из общего числа: это работает только для одного запрета и легко приводит к двойному вычитанию.
Для нескольких запретов удалите все сразу.

Пример

В графе из метода 02 без вершины D остаются пути A–B–E–F–G–H, A–B–E–G–H, A–C–E–F–G–H, A–C–E–G–H. Их 4. В задаче № 21836 после удаления B из графа остаётся 5 путей.

Ответ4 (для графа из метода 02).

По мотивам задач № 21836 и № 285.

когда условий два и больше

Комбинации условий: «через X, но не через Y»

Когда использовать: Встречаются «через X и Y», «через X, но не через Y», «хотя бы через один из X, Y».

«Через X, но не через Y»: сначала удалите Y, затем примените правило умножения для X.
«Через X и Y»: перемножьте пути A → X, X → Y, Y → B.
Если порядок X и Y не указан, сложите варианты X → Y и Y → X; пути, проходящие обе вершины, не считайте дважды.
«Хотя бы через одну из X или Y»: N(X) + N(Y) − N(X и Y).
Проверьте результат перебором на небольшом графе.

Пример

В графе из метода 02: через E — 8 путей, через B — 5, через обе — 4. Тогда «через B или E» = 5 + 8 − 4 = 9. «Через E, но не через D» = 4.

Ответ9 и 4.

По мотивам задач № 270 и № 285.

когда у рёбер есть веса

Кратчайший путь: Дейкстра

Когда использовать: Нужно найти минимальную сумму длин рёбер из A в B.

Постройте список смежности с весами.
Задайте dist[start] = 0, для остальных — бесконечность.
Выберите непосещённую вершину с минимальным dist.
Для каждого соседа проверьте, не станет ли путь короче: dist[u] + w < dist[v].
Запоминайте предыдущую вершину, чтобы восстановить маршрут.
Ответ — dist[finish]; маршрут восстанавливается по prev.

Пример

Граф: A→B(4), A→C(2), B→C(1), B→D(5), C→D(8), C→E(10), D→E(2), D→F(6), E→F(3). Кратчайший путь A→F: A–B–D–E–F = 4 + 5 + 2 + 3 = 14.

from heapq import heappush, heappop

graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('C', 1), ('D', 5)],
    'C': [('D', 8), ('E', 10)],
    'D': [('E', 2), ('F', 6)],
    'E': [('F', 3)],
    'F': [],
}

dist = {v: float('inf') for v in graph}
dist['A'] = 0
prev = {}
pq = [(0, 'A')]
while pq:
    d, v = heappop(pq)
    if d != dist[v]:
        continue
    for u, w in graph[v]:
        if d + w < dist[u]:
            dist[u] = d + w
            prev[u] = v
            heappush(pq, (d + w, u))
print(dist['F'])  # 14

Ответ14.

По мотивам задач № 31518 и № 38.

когда дан файл с рёбрами

Граф в файле: парсинг и рекурсия

Когда использовать: В файле записаны тройки L M W, граф ациклический, нужно найти кратчайший путь или количество путей.

Прочитайте файл построчно и разбейте каждую строку через split().
Постройте словарь: из вершины L — список пар (M, W).
Не предполагайте, что вершины пронумерованы подряд: используйте словарь, а не массив.
Для кратчайшего пути в DAG подойдёт рекурсия с lru_cache или Дейкстра.
Если веса вещественные, не забудьте взять целую часть только в самом конце.
Проверьте, что старт и финиш взяты из условия, а не из примера.

Пример

В задаче № 31518 дан ациклический взвешенный граф: до 1000 вершин, до 200 рёбер, веса до 10 000. Нужно найти целую часть кратчайшего пути из 1 в 100. Ответ — 10 971.

from collections import defaultdict
from functools import lru_cache

g = defaultdict(list)
for line in open('23.txt'):
    L, M, W = line.split()
    g[int(L)].append((int(M), float(W)))

@lru_cache(None)
def best(v):
    if v == 100:
        return 0
    if v not in g:
        return float('inf')
    return min(w + best(u) for u, w in g[v])

print(int(best(1)))  # 10971

Ответ10 971.

Задача № 31518 (база Kompege), видеоразбор на Rutube.

когда нужен список путей или проверка

Перебор путей и проверка

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

Запустите DFS из стартовой вершины.
Добавляйте вершину в текущий путь.
При достижении финиша выведите путь и увеличьте счётчик.
В графе с циклами отмечайте посещённые вершины, иначе обход зациклится.
Сравните число найденных путей с ответом динамики.

Пример

Для графа из теории DFS выводит 6 путей: А–Б–Д–К, А–Б–В–К, А–Б–К, А–Г–В–К, А–Г–К, А–Г–Е–К.

graph = {
    'А': ['Б', 'Г'],
    'Б': ['Д', 'В', 'К'],
    'Г': ['В', 'К', 'Е'],
    'В': ['К'],
    'Д': ['К'],
    'Е': ['К'],
    'К': [],
}

def dfs(v, path):
    if v == 'К':
        print('–'.join(path + [v]))
        return
    for u in graph[v]:
        dfs(u, path + [v])

dfs('А', [])

Ответ6 путей.

По мотивам задач № 21834 и № 21835.

когда условие отличается от шаблона

Нестандартные формулировки

Когда использовать: Встречаются пути через ребро, ровно k рёбер, циклы, неориентированный граф или несколько стартов.

Через ребро X→Y: N(A→X) × N(Y→B), само ребро добавляет один переход.
Ровно k рёбер: заведите dp[k][v] и пересчитывайте по слоям; обычная динамика по вершинам здесь не подходит.
Граф с циклом: путей может быть бесконечно много; если длина ограничена, считайте по числу шагов.
Неориентированный граф: каждое ребро можно проходить в обе стороны, но путь не должен возвращаться назад без необходимости.
Несколько рёбер между одной парой вершин считаются разными путями, если они различны.
Старт и финиш могут быть заданы номерами, а не буквами; подставьте их аккуратно.
Если просят «укажите путь», восстановите его по prev и запишите вершины подряд.

По мотивам задач № 270, № 285 и № 1331.

Шпаргалка: формулировка → метод

В условии	Что делать
«сколько существует различных путей»	динамика: dp[v] = Σ dp[u]
«проходящих через X»	N(A→X) × N(X→B)
«не проходящих через X»	удалить X и считать заново
«через X, но не через Y»	удалить Y, затем умножить участки через X
«хотя бы через одну из X, Y»	N(X) + N(Y) − N(X и Y)
«кратчайший путь / оптимальный маршрут»	Дейкстра или динамика по DAG
«дана таблица длин дорог»	сопоставить вершины и построить список смежности
«дан файл L M W»	парсинг + Дейкстра или рекурсия
«ровно k рёбер»	dp по числу шагов
«перечислите пункты маршрута»	восстановить путь по prev

Видеоразборы по теме

Видеоразборы открытого курса КомпЕГЭ; для заданий 8–12 и 27 — дополнительные разборы демоверсии 2027.

По базе Kompege: 195 задач с формулировкой «различных путей» (в том числе 95 в старой нумерации 113) и 10 задач на кратчайший путь. Использованы задачи № 12, 57, 96, 214, 270, 285, 291, 21834–21836 и 31518; формулировки и примеры переработаны в учебные.

Разборы из видео

Задачи, которые разбирают в курсе

Условия и код показаны в кадре в конце соответствующего фрагмента. Источники задач — КомпЕГЭ, сайт К. Полякова, ФИПИ и другие.

№ 31523

разбор из видео · 2027

Кратчайший путь в файле

В файле описание ациклического ориентированного взвешенного графа: L, M, W. Найдите целую часть длины кратчайшего пути из вершины 3 в вершину 97.

d = {}
for s in open('23_31523.txt'):
    frm, to, w = [float(x) for x in s.split()]
    if frm not in d:
        d[frm] = []
    d[frm].append((to, w))

def f(c, e):
    if c == e:
        return 0
    if c not in d:
        return 10**10
    return min(f(to, e) + w for to, w in d[c])

print(f(3, 97))

Ответ315

Смотреть с 07:25

№ 31599

разбор из видео · 2027

Кратчайший путь через вершину 50

В файле ориентированный взвешенный граф. Найдите целую часть длины кратчайшего пути из 9 в 92, который обязательно проходит через вершину 50.

Ответ852

Смотреть с 41:55

Полный архив

Все фрагменты видеоразборов

По одному пункту на каждую главу: условие или код из кадра, ответ и ссылка. Источники задач — КомпЕГЭ, сайт К. Полякова, ФИПИ и другие; номер берётся из кадра. Текст с экрана распознан автоматически, служебные строки и артефакты удалены; если текст нечитаем, остаются название, таймкод и ссылка.

Показать все фрагменты (12)

2027 · 00:00 Приветствие

В каждой строке файла записаны два натуральных числа (L. М) и одно положительное вещественное число (№). Ги М — номера вершин графа, W — вес ребра, могут быть соединены более чем одним ребром. "Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 3 в вершину с номером 97. Существование хотя "бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь. Для выполнения этого задания следует написать программу. Вершины графа могут быть пронумерованы не подряд. Количество строк в файле не превосходит 200

Смотреть с 00:00

2027 · 07:25 Поиск кратчайшего пути

В каждой строке файла записаны два натуральных числа (L. М) и одно положительное вещественное число (1). Ги М — номера вершин графа, W — вес ребра, могут быть соединены более чем одним ребром. "Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 3 в вершину с номером 97. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь. Для выполнения этого задания следует написать программу. Вершины графа могут быть пронумерованы не подряд. Количество строк в файле не превосходит 200.

for 3 in open('23_31523.txt'):
if cete; return @

Смотреть с 07:25

2027 · 29:30 Поиск пути наибольшей длины 31526

В каждой строке файла записаны два натуральных числа (- М) и одно положительное вещественное число (W). и М - номера вершин графа, W - вес ребра, "ведущего из вершины L в вершину М. Таким образом, количество строк в "файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром. Найдите и запишите в ответе целую часть пути наибольшей длины из вершины с номером 4 в вершину с номером 96. Существование хотя бы "одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, составляющих путь. "Для выполнения этого задания следует написать прогр

def F(c,e)
return max(f(to,e)+w for to,w in d[c])
return 0 — oa ——

Смотреть с 29:30

2027 · 32:45 Кратчайший путь, НЕ проходящий через вершину 3152

Шастин) В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла ведущего из вершины L в вершину М. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром. "Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 514 в вершину с номером 7836, не проходящего через вершину с номером 3260. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается "минимальная сумма весов рёбер, составляющих путь. "na выполнения этого задания следует написать программу. Вершины графа могут быть пронумерованы не подр

from functools import *
def f(c,e)
print(f(514,7836))

Смотреть с 32:45

2027 · 37:55 Кратчайший путь, проходящий через вершину

if ¢ return @
return min(f(to,e)+w for to,w in d[c])

Смотреть с 37:55

2027 · 41:55 Кратчайший путь, проходящий через ребро

(А Богданов) В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, М) и одно положительное вещественное число (W). L и М - номера вершин графа, W — вес ребра, могут быть соединены более чем одним ребром. Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 9 в вершину с номером 92. обязательно, "содержащего ребро из вершины 25 в вершину 50. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути "понимается минимальная сумма весов рёбер, составляющих путь. "строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

from functools import *
def F(c,e)
print(f(9,25)+xf+f(50,92))

Смотреть с 41:55

2027 · 47:55 Путь наибольшей длины, не превышающей 2000

{А.Богданов) В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (1, М) и одно положительное вещественное число (W). 1 и М — номера вершин графа, W — вес ребра, ведущего из вершины L в вершину М. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром. найдите и запишите в ответе целую часть пути наибольшей длины, не превыщающей 2000, из вершины с номером 12 в вершину с — номером 89. Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, составляющих Apa выполнения этого задания

return max(f(to,e,s+w) for to,w in d[c])
print(f(12,89,0))

Смотреть с 47:55

2027 · 1:03:15 Кратчайший путь длиной не менее 2000

Шести) В текстовом Файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, М) и одно положительное вещественное число (W). Lm М - номера вершин графа, W - вес ребра, ведущего из вершины L в вершину М. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром. Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1207 в вершину с номером 7613, содержащего не "более К = 20 рёбер. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составл

Смотреть с 1:03:15

2027 · 1:08:00 Кратчайший путь, содержащий не более K рёбер

Шастин) В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, М) и одно положительное вещественное число (W). Г иМ - номера вершин графа, W — вес ребра, ведущего из вершины L в вершину М. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром. 'Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1207 в вершину с номером 7613, содержащего не "более К = 20 рёбер. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма.

from functools import *
return min(f(to,e,k+1)+w for to,w in d[c])

Смотреть с 1:08:00

2027 · 1:15:35 Минимальное количество рёбер в пути

Шастин) В текстовом Файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла могут быть соединены более чем одним ребром. Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером 1207 в вершину с номером 7613, содержащего HE "более К = 20 рёбер. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь. ‚Для выполнения этого задания следует написать программу. Вершины графа могут быть пронумерованы не подряд, L < 10000, М < 10000; Количество строк в файле не превосходит 100 000. Числа в строках разделены произвольным ненулевым количеством п

from functools import *
return min(f(to,e,k+1)+w for to,w in 9[c])

Смотреть с 1:15:35

2027 · 1:20:25 Количество путей между вершинами 3157

(Богданов) В текстовом Файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла l0oJIO ведущего из вершины LB вершину М. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром. Найдите и запишите в ответе количество различных путей из вершины с номером 14 в вершину с номером 88. Существование хотя бы одного такого пути гарантируется. ‚Для выполнения этого задания следует написать программу. Вершины графа могут быть пронумерованы не подряд. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

def f(c,e):
if return 1
return sum(f(to,e) for to,w in 9[<])
print( (14,88) )

Смотреть с 1:20:25

2027 · 1:22:40 Окончание и напутствие

В этом фрагменте — теория или пояснение; решение показано в видео.

Смотреть с 1:22:40

Типичные ошибки

игнорируют направление стрелок и считают обратные пути
обрабатывают вершины не в топологическом порядке и теряют пути
путают количество путей с количеством рёбер
умножают вместо сложения на участках или складывают вместо умножения
забывают удалить запрещённую вершину или её входящие рёбра
применяют Дейкстру к графу с отрицательными весами
берут не тот старт или финиш, забывают целую часть в ответе

Ключевые формулы

dp[start] = 1, dp[v] = Σ dp[u] по всем рёбрам u → v
N(A → B через X) = N(A → X) × N(X → B)
N(A → B, не через X) = N(A → B в графе без X)
dist[v] = min(dist[u] + w(u, v))
N(X или Y) = N(X) + N(Y) − N(X и Y)

Практика

ФИПИОткрытый банк заданий Навигатор · 2026Алгоритмы ДемоверсияКИМ 2027 МетодикаРазбор ошибок 2026

В навигаторе 2026 отдельной темы по графам нет: тренируйтесь по открытому банку ФИПИ и демоверсии 2027 года.