Между городами А, Б, В, Г, Д, Е, Ж, З, И, К, Л заданы дороги с односторонним движением.
Ниже перечислены все дороги. Число в скобках — стоимость проезда по дороге в условных единицах.
Из А — в Б (3), Г (4).
Из Б — в В (1), Г (4).
Из В — в Г (4), Д (1), Ж (3).
Из Г — в Д (1), Е (2), И (3).
Из Д — в Е (2), И (3).
Из Е — в Ж (4), З (1).
Из Ж — в З (1), И (2).
Из З — в И (1), К (4).
Из И — в К (2), Л (4).
Из К — в Л (1).
Других дорог нет. По дороге можно двигаться только в указанном направлении. Все дороги ведут к городам, стоящим правее в приведённом списке, поэтому циклов нет.
Стоимость пути равна сумме стоимостей его дорог. Два пути считаются различными, если различаются последовательности посещённых городов.
Сколько существует путей из А в Л, которые проходят через Е и имеют стоимость ровно 16?
Ответ и разбор
Ответ: 12
Разобьём путь в обязательном городе Е. В ациклическом графе он встречается не более одного раза: любой подходящий путь однозначно состоит из участка А → Е и участка Е → Л.
Одних общих чисел путей на участках недостаточно: их стоимости должны в сумме дать ровно 16. Сохраняем отдельный счётчик для каждой стоимости.
F(v, s) — число путей из А в v со стоимостью ровно s. База F(А, 0) = 1: это единственный пустой путь в начальный город, без дорог и затрат. Остальные начальные состояния равны 0.
Считаем вершины в приведённом порядке. Для каждой входящей дороги u → v стоимости c прибавляем F(u, s − c) к F(v, s). Каждое продолжение имеет единственную последнюю дорогу, поэтому такой подсчёт не теряет и не дублирует пути; при отрицательной стоимости значение равно 0.
В списках запись «стоимость → количество» означает число путей именно этой стоимости. Показаны все ненулевые состояния, без отсечения по бюджету; не перечисленные стоимости имеют количество 0.
Первый участок: А → Е, распределения F:
- Город А: 0 → 1.
- Город Б: 3 → 1.
- Город В: 4 → 1.
- Город Г: 4 → 1; 7 → 1; 8 → 1.
- Город Д: 5 → 2; 8 → 1; 9 → 1.
- Город Е: 6 → 1; 7 → 2; 9 → 1; 10 → 2; 11 → 1.
Проверка: F(Д, 5) = F(В, 4) + F(Г, 4) = 1 + 1 = 2 — клетка сходится.
Второй участок: Е → Л, распределения G. Начинаем заново с G(Е, 0) = 1 (пустой путь); переход тот же.
- Город Е: 0 → 1.
- Город Ж: 4 → 1.
- Город З: 1 → 1; 5 → 1.
- Город И: 2 → 1; 6 → 2.
- Город К: 4 → 1; 5 → 1; 8 → 2; 9 → 1.
- Город Л: 5 → 1; 6 → 2; 9 → 2; 10 → 3.
Проверка: G(И, 6) = G(Ж, 4) + G(З, 5) = 1 + 1 = 2 — клетка сходится.
Сочетаем только дополняющие стоимости: если первый участок стоит s, второй должен стоить 16 − s. Для фиксированной пары любой первый путь можно соединить с любым вторым: ранние и поздние вершины не пересекаются, кроме Е. Разные пары стоимостей не смешиваются.
- 6 + 10 = 16: 1 · 3 = 3.
- 7 + 9 = 16: 2 · 2 = 4.
- 10 + 6 = 16: 2 · 2 = 4.
- 11 + 5 = 16: 1 · 1 = 1.
Другие пары не дают нужной суммы или имеют нулевое количество путей. Всего: 3 + 4 + 4 + 1 = 12.
Частая ошибка
Ловушка: произведение общих чисел путей учитывает и другие стоимости; подсчёт всех путей нужной стоимости дополнительно захватил бы пути в обход Е.
Нашли ошибку? Напишите нам, код задания: stg-ege-informatics-paths-high-11
Открыть тренажёр