Информатика, задание 23 ЕГЭ-2027: графы — число путей и оптимальный путь

Ответ: 13

1. Шаг 1. Число путей в город — сумма чисел путей в города, из которых в него ведёт дорога. Для начального города А: 1.
2. Шаг 2. Идём по городам в порядке дорог: Б = А = 1; В = Б = 1; Г = А = 1; Д = Б + В = 2; Е = Г + Д = 3; Ж = Г + Е = 4; З = Д + Е + Ж = 9; И = Ж + З = 13.
3. Шаг 3. В конечном городе И получилось 13 — это и есть ответ.
4. Шаг 4. Проверка: полный перебор путей программой дал то же число — 13.

Ответ: 21

1. Шаг 1. Число путей в город — сумма чисел путей в города, из которых в него ведёт дорога. Для начального города А: 1.
2. Шаг 2. Идём по городам в порядке дорог: Б = 0; В = А = 1; Г = А = 1; Д = Б + В = 1; Е = В + Г + Д = 3; Ж = Г + Д + Е = 5; З = Ж = 5; И = Е + З = 8; К = З + И = 13; Л = К = 13; М = И + К = 21; Н = Л + М = 34.
3. Шаг 3. Путь обязан пройти через В: путей до В — 1, путей от В до Н (считаем так же, начав с 1 в В) — 21. Перемножаем: 1 · 21 = 21.
4. Шаг 4. Проверка: полный перебор путей программой дал то же число — 21.

Ответ: 8

1. Шаг 1. Число путей в город — сумма чисел путей в города, из которых в него ведёт дорога. Для начального города А: 1.
2. Шаг 2. Идём по городам в порядке дорог: Б = А = 1; В = 0; Г = А + Б + В = 2; Д = В = 0; Е = Г + Д = 2; Ж = Г + Е = 4; З = Ж = 4; И = Ж + З = 8; К = И = 8; Л = К = 8.
3. Шаг 3. В конечном городе Л получилось 8 — это и есть ответ.
4. Шаг 4. Проверка: полный перебор путей программой дал то же число — 8.

Ответ: 8

1. Шаг 1. Число путей в город — сумма чисел путей в города, из которых в него ведёт дорога. Для начального города А: 1.
2. Шаг 2. Идём по городам в порядке дорог: Б = А = 1; В = Б = 1; Г = А = 1; Д = Б + В = 2; Е = В + Г = 2; Ж = Д + Е = 4; З = Д + Е = 4; И = Ж + З = 8; К = 0; Л = И + К = 8; М = Л = 8; Н = Л + М = 16.
3. Шаг 3. Путь обязан пройти через З: путей до З — 4, путей от З до Н (считаем так же, начав с 1 в З) — 2. Перемножаем: 4 · 2 = 8.
4. Шаг 4. Проверка: полный перебор путей программой дал то же число — 8.

Ответ: 27

1. Шаг 1. Число путей в город — сумма чисел путей в города, из которых в него ведёт дорога. Для начального города А: 1.
2. Шаг 2. Идём по городам в порядке дорог: Б = А = 1; В = 0; Г = А + Б = 2; Д = Б + Г = 3; Е = В + Д = 3; Ж = Г + Д + Е = 8; З = Ж = 8; И = Е + Ж + З = 19; К = 0; Л = З + К = 8; М = И + К + Л = 27.
3. Шаг 3. В конечном городе М получилось 27 — это и есть ответ.
4. Шаг 4. Проверка: полный перебор путей программой дал то же число — 27.

Ответ: 8

1. Шаг 1. Число путей в город — сумма чисел путей в города, из которых в него ведёт дорога. Для начального города А: 1.
2. Шаг 2. Идём по городам в порядке дорог: Б = 0; В = А + Б = 1; Г = 0; Д = Б + В = 1; Е = Д = 1; Ж = Г + Е = 1; З = Е = 1; И = Ж + З = 2; К = Ж + З = 2; Л = И + К = 4; М = И + Л = 6; Н = Л + М = 10.
3. Шаг 3. Путь обязан пройти через Л: путей до Л — 4, путей от Л до Н (считаем так же, начав с 1 в Л) — 2. Перемножаем: 4 · 2 = 8.
4. Шаг 4. Проверка: полный перебор путей программой дал то же число — 8.

Ответ: 17

1. Шаг 1. Число путей в город — сумма чисел путей в города, из которых в него ведёт дорога. Для начального города А: 1.
2. Шаг 2. Идём по городам в порядке дорог: Б = А = 1; В = Б = 1; Г = А = 1; Д = Б + В = 2; Е = В + Г + Д = 4; Ж = Г = 1; З = Д + Е = 6; И = Е + Ж + З = 11; К = З + И = 17; Л = К = 17.
3. Шаг 3. В конечном городе Л получилось 17 — это и есть ответ.
4. Шаг 4. Проверка: полный перебор путей программой дал то же число — 17.

Ответ: 8

1. Шаг 1. Число путей в город — сумма чисел путей в города, из которых в него ведёт дорога. Для начального города А: 1.
2. Шаг 2. Идём по городам в порядке дорог: Б = А = 1; В = Б = 1; Г = А = 1; Д = В + Г = 2; Е = В + Г + Д = 4; Ж = 0; З = Е = 4; И = Е + З = 8; К = Ж + И = 8; Л = З + К = 12; М = Л = 12.
3. Шаг 3. Путь обязан пройти через И: путей до И — 8, путей от И до М (считаем так же, начав с 1 в И) — 1. Перемножаем: 8 · 1 = 8.
4. Шаг 4. Проверка: полный перебор путей программой дал то же число — 8.

Ответ: 55012

1. Шаг 1. Граф ациклический, поэтому самый длинный путь ищется динамикой: best[v] = max(best[u] + w) по всем рёбрам u → v.
2. Шаг 2. Вершины обходятся в топологическом порядке: к моменту расчёта v все её предшественники уже посчитаны.
3. Шаг 3. Алгоритм Дейкстры здесь не годится — он ищет кратчайший путь; для длинного пути нужна именно динамика по порядку.
4. Шаг 4. В графе 1100 вершин и 4382 рёбер. Динамика по топологическому порядку даёт длину самого длинного пути 55012. Ответ: 55012.

from graphlib import TopologicalSorter
edges = [tuple(map(int, s.split())) for s in open('23.txt')]
prev = {}
for a, b, w in edges: prev.setdefault(b, []).append((a, w)); prev.setdefault(a, [])
best = {1: 0}
for v in TopologicalSorter({v: [a for a, _ in p] for v, p in prev.items()}).static_order():
    c = [best[a] + w for a, w in prev[v] if a in best]
    if c and v != 1: best[v] = max(c)
print(best[N])  # N — номер конечной вершины из условия

Ответ: 79608

1. Шаг 1. Граф ациклический, поэтому самый длинный путь ищется динамикой: best[v] = max(best[u] + w) по всем рёбрам u → v.
2. Шаг 2. Вершины обходятся в топологическом порядке: к моменту расчёта v все её предшественники уже посчитаны.
3. Шаг 3. Алгоритм Дейкстры здесь не годится — он ищет кратчайший путь; для длинного пути нужна именно динамика по порядку.
4. Шаг 4. В графе 1547 вершин и 6172 рёбер. Динамика по топологическому порядку даёт длину самого длинного пути 79608. Ответ: 79608.

from graphlib import TopologicalSorter
edges = [tuple(map(int, s.split())) for s in open('23.txt')]
prev = {}
for a, b, w in edges: prev.setdefault(b, []).append((a, w)); prev.setdefault(a, [])
best = {1: 0}
for v in TopologicalSorter({v: [a for a, _ in p] for v, p in prev.items()}).static_order():
    c = [best[a] + w for a, w in prev[v] if a in best]
    if c and v != 1: best[v] = max(c)
print(best[N])  # N — номер конечной вершины из условия