Что спрашивают
Нужно посчитать различные пути из 11 в 97. Пути различаются последовательностями вершин. В графе нет циклов и параллельных рёбер; хотя бы один путь существует. Веса прочитать нужно, но для подсчёта они не используются.
Граф может быть небольшим, а число путей — большим: на каждом из нескольких слоёв есть развилка. Перечисление всех последовательностей быстро становится слишком медленным.
Приём решения
Пусть ways(v) — число путей из вершины v до финиша. На финише ways(97) = 1: существует один способ закончить уже построенный путь, больше не делая шагов.
В остальных вершинах складываем ответы всех исходящих соседей: ways(v) = sum(ways(u)) по рёбрам v → u. У тупика сумма пуста и равна нулю. Минимум и максимум здесь не нужны — они выбрали бы одну ветвь, а посчитать нужно все.
- Сохраним исходящих соседей, отбросив веса.
- В рекурсивной функции вернём единицу на заданном финише.
- Для любой другой вершины сложим числа продолжений по всем соседям.
- Поставим кеш, чтобы общий хвост разных путей вычислялся один раз.
Почему сумма не считает один путь дважды? Группы путей по первому ребру не пересекаются: разные первые соседи уже дают разные последовательности вершин. Если ветви позже сходятся, их общие продолжения всё равно относятся к разным путям от старта. Поэтому глобальный флаг «вершина уже посещена» здесь не заменяет кеш.
Каждая вершина вычисляется один раз, каждое исходящее ребро просматривается один раз: O(V + E) сложений, память O(V + E). Числа путей могут расти быстро; Python int хранит их без переполнения фиксированного целого типа.
Разбор на примере
Ввод
11 80 1.0 11 60 1.0 80 20 1.0 60 20 1.0 20 97 1.0 11 97 8.0 11 9 0.1
Вывод
3
- Из
97один способ закончить путь, поэтому из20тоже один. - Из
80и из60по одному продолжению через20. Его значение переиспользуется, но обе ветви учитываются. - Из
9продолжений нет. У старта складываем пути через80, через60, прямой путь и тупик через9:1 + 1 + 1 + 0 = 3.
Код на Python и C++
Короткая запись sum(...) возвращает ноль для пустого списка соседей. Единица появляется только на заданном финише, чтобы успешно завершённый путь был учтён.
В C++ сумма по соседям считается обычным циклом от нуля. Число путей хранится в long long: по условию оно меньше 263 и помещается в этот тип, а в int уже нет.
import sys
from functools import lru_cache
sys.setrecursionlimit(5000)
graph = {}
for line in sys.stdin:
parts = line.split()
if not parts:
continue
a, b, _ = parts
graph.setdefault(int(a), []).append(int(b))
lru_cache(None)
def ways(v):
if v == 97:
return 1
return sum(ways(u) for u in graph.get(v, []))
print(ways(11))
<iostream>
<map>
<string>
<vector>
using namespace std;
map<int, vector<int>> graph;
void read_graph() {
int a, b;
string weight;
while (cin >> a >> b >> weight)
graph[a].push_back(b);
}
map<int, long long> memo;
long long ways(int v) {
if (v == 97)
return 1;
if (memo.count(v))
return memo[v];
long long total = 0;
for (int u : graph[v])
total += ways(u);
return memo[v] = total;
}
int main() {
read_graph();
cout << ways(11) << endl;
}
Типичные ошибки
- Вернуть ноль на финише
Тогда все суммы выше также будут нулевыми. Завершённый путь должен вносить в число вариантов единицу.
- Брать максимум по соседям
Максимум считает только наиболее богатую продолжениями ветвь. Разные первые рёбра задают разные группы путей, их количества складываются.
- Отсечь повторный вход глобальным visited
Общая вершина может принадлежать нескольким путям. Её ответ нужно повторно использовать, а не считать повторный вход запретом.
- Перечислять все полные пути
Их количество может быть огромным. Динамика хранит только число продолжений каждой вершины.