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

Требуется кратчайший путь из 11 в 97, не проходящий через вершину 67. Ответом служит целая часть его длины. Граф ориентированный и ациклический; разрешённый путь существует.

Наличие очень короткого пути через запрещённую вершину ничего не говорит об ответе. Сравнивать нужно только пути, которые выполняют запрет.

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

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

В коде удалять рёбра необязательно. Пусть shortest(67) сразу возвращает None. Любой переход в неё будет отвергнут как недопустимое продолжение. Удалять только исходящие рёбра менее явно: запрет относится к самой вершине, а не к способу покинуть её.

  1. Прочитаем все ориентированные рёбра до конца ввода.
  2. При входе в запрещённую вершину вернём None, а при входе в финиш — ноль.
  3. Для остальных вершин переберём допустимые продолжения и выберем минимальную сумму.
  4. Веса сохраним целыми десятыми долями и возьмём целую часть только у итоговой длины.

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

Каждый разрешённый путь полностью лежит в оставшемся графе, и каждый путь этого графа разрешён. Поэтому обычный минимум после удаления даёт нужный ответ. Время и память — O(V + E).

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

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

Ввод

11 67 0.2
67 97 0.3
11 80 1.6
80 20 0.7
20 97 2.2
11 97 6.1

Вывод

4
  1. Путь через 67 имел бы длину 0.5, но исключается до сравнения длин.
  2. В разрешённой части графа есть прямой путь длины 6.1 и путь 11 → 80 → 20 → 97 длины 1.6 + 0.7 + 2.2 = 4.5.
  3. Выбираем 4.5 и выводим 4. Убывание номеров на ребре 80 → 20 допустимо.

Код на Python и C++

Запрет проверяется до перебора продолжений. Значение None означает отсутствие допустимого пути; ноль оставлен для достижения финиша.

В C++ запрещённая вершина возвращает NO_PATH = -1 вместо None, а найденные значения лежат в словаре map<int, long long> memo.

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):
    if v == 67:
        return None
    if v == 97:
        return 0
    best = None
    for u, w in graph.get(v, []):
        tail = shortest(u)
        if tail is not None:
            candidate = w + tail
            if best is None or candidate < best:
                best = candidate
    return best


print(shortest(11) // 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<int, long long> memo;

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

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

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

  • Сначала выбрать кратчайший путь без запрета

    Если найденный путь запрещён, его удаления недостаточно: нужно заново искать лучший среди всех разрешённых продолжений.

  • Возвращать ноль для запрещённой вершины

    Так она превращается в дополнительный финиш. Возвращайте None и пропускайте такие продолжения при выборе минимума.

  • Округлять веса до суммирования

    Для корректного сравнения сохраняйте дробные части. Целые десятые доли дают точную сумму без погрешности.

  • Перебирать все полные пути

    Разные ветви могут сходиться в одной вершине. Запоминайте ответ этой вершины, чтобы не вычислять её продолжения многократно.