Что спрашивают

Нужно найти кратчайший путь из 11 в 97, содержащий ребро 53 → 29. Недостаточно отдельно посетить вершины 53 и 29: переход между ними должен быть именно этим ребром и именно в указанном направлении.

Граф ориентированный и ациклический, допустимый путь существует. Выводится целая часть его длины; вес каждого ребра записан с одной цифрой после точки.

Приём решения

Добавим к номеру вершины флаг used: пройдено ли обязательное ребро на пути от старта до текущего места. Функция shortest(v, used) возвращает минимальную длину ещё не пройденного участка до финиша при таком состоянии.

Для перехода v → u новый флаг равен used or (v, u) == (53, 29). После нужного ребра флаг остаётся истинным на всех последующих шагах. На финише возвращаем ноль только при истинном флаге, иначе None: прийти к финишу без выполнения условия нельзя.

  1. Соберём список исходящих рёбер с весами в десятых долях.
  2. Начнём вычисление из состояния (11, False).
  3. На каждом ребре обновим флаг, запросим лучшее продолжение и добавим вес перехода.
  4. Из всех допустимых продолжений выберем минимум. В конце разделим общую длину на десять.

У одной вершины могут быть два разных ответа: до прохождения обязательного ребра и после него. Именно поэтому флаг входит в аргументы кешируемой функции. Состояние описывает всю нужную предысторию; конкретный список уже пройденных вершин в графе без циклов хранить не нужно.

Каждый допустимый путь возникает среди переходов с нужным обновлением флага, а финиш отсекает все недопустимые. На вершину приходится не более двух состояний; время и память — O(V + E). Другой вариант решения — сложить расстояние до начала обязательного ребра, его вес и расстояние от его конца до финиша.

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

Ориентированный граф из примера; числа на стрелках — веса рёбер1.22.61.70.10.20.41153802997

Ввод

11 53 1.2
53 29 2.6
29 97 1.7
53 80 0.1
80 29 0.2
11 97 0.4

Вывод

5
  1. Прямое ребро 11 → 97 приводит к финишу с used = False и отвергается.
  2. Путь 11 → 53 → 80 → 29 → 97 проходит через обе нужные вершины, но пропускает ребро 53 → 29. Он тоже не подходит.
  3. На разрешённом пути флаг меняется при переходе 53 → 29. Его длина 1.2 + 2.6 + 1.7 = 5.5, поэтому выводим 5.

Код на Python и C++

Кеш учитывает оба аргумента. В корневом вызове флаг ложен; изменять его можно только на конкретном обязательном ребре.

В C++ ключ словаря memo — пара {v, used}, флаг имеет тип bool, а or записывается как ||.

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, text = parts
    whole, tenth = text.split('.')
    weight = int(whole) * 10 + int(tenth)
    graph.setdefault(int(a), []).append((int(b), weight))


@lru_cache(None)
def shortest(v, used):
    if v == 97:
        return 0 if used else None
    best = None
    for u, w in graph.get(v, []):
        new_used = used or (v, u) == (53, 29)
        tail = shortest(u, new_used)
        if tail is not None:
            candidate = w + tail
            if best is None or candidate < best:
                best = candidate
    return best


print(shortest(11, False) // 10)
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
using namespace std;

const long long NO_PATH = -1;
map<int, vector<pair<int, long long>>> graph;

void read_graph() {
    int a, b;
    string text;
    while (cin >> a >> b >> text) {
        size_t dot = text.find('.');
        long long weight = stoll(text.substr(0, dot)) * 10 + stoll(text.substr(dot + 1));
        graph[a].push_back({b, weight});
    }
}

map<pair<int, bool>, long long> memo;

long long shortest(int v, bool used) {
    if (v == 97)
        return used ? 0 : NO_PATH;
    if (memo.count({v, used}))
        return memo[{v, used}];
    long long best = NO_PATH;
    for (auto [u, w] : graph[v]) {
        bool new_used = used || (v == 53 && u == 29);
        long long tail = shortest(u, new_used);
        if (tail != NO_PATH) {
            long long candidate = w + tail;
            if (best == NO_PATH || candidate < best)
                best = candidate;
        }
    }
    return memo[{v, used}] = best;
}

int main() {
    read_graph();
    cout << shortest(11, false) / 10 << endl;
}

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

  • Проверять только посещение концов ребра

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

  • Забыть направление

    Ребро 53 → 29 не равно ребру 29 → 53. Сравнивайте упорядоченную пару начала и конца перехода.

  • Сбрасывать флаг после следующего шага

    Флаг означает «когда-либо уже пройдено». Используйте логическое or, чтобы выполненное условие оставалось выполненным.

  • Запоминать ответ только по вершине

    Разрешённые продолжения зависят от того, выполнено ли требование раньше. Ключ кеша должен включать этот флаг.