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

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

Ответ — целая часть полной длины разрешённого пути. Самый короткий путь вообще и самый короткий путь через контрольную вершину могут нарушать запрет, поэтому ни один из них нельзя автоматически принять за ответ.

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

Сначала исключим запрещённую вершину 67 из всех вычислений. После этого разделим путь в обязательной вершине 53: нужно сложить кратчайшее расстояние 11 → 53 и кратчайшее расстояние 53 → 97. Оба расстояния считаются в одном и том же графе с запретом.

Определим shortest(v, target). При v == 67 получаем None, при достижении выбранной цели — ноль. Для каждой другой вершины берём минимум по достижимым продолжениям. Цель входит в ключ кеша; запрет зафиксирован внутри функции.

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

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

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

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

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

Ввод

11 53 2.4
11 67 0.1
67 53 0.2
53 97 4.2
53 20 1.1
20 97 1.6
11 97 0.5

Вывод

5
  1. Прямое ребро к финишу пропускает 53. Дешёвый участок 11 → 67 → 53 нарушает запрет.
  2. Разрешённое расстояние до контрольной вершины равно 2.4.
  3. После неё сравниваем прямое продолжение 4.2 и продолжение через 20 длины 1.1 + 1.6 = 2.7.
  4. Итоговая длина 2.4 + 2.7 = 5.1; целая часть — 5.

Код на Python и C++

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

В C++ ключ словаря memo — пара {v, target}, запрещённая вершина возвращает NO_PATH = -1 вместо None.

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


total = shortest(11, 53) + shortest(53, 97)
print(total // 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, int>, long long> memo;

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

int main() {
    read_graph();
    long long total = shortest(11, 53) + shortest(53, 97);
    cout << total / 10 << endl;
}

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

  • Учесть только одно требование

    Путь может пройти через контрольную вершину, но задеть запрещённую, или обойти запрет, но пропустить контрольную. Проверяются оба ограничения.

  • Применить запрет только на одном участке

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

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

    Целая часть берётся от полной суммы. Потерянные дробные части участков могут изменить ответ.

  • Переиспользовать кеш для разных целей без ключа

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