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

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

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

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

Любой допустимый путь делится в вершине 53 на два участка: от старта до контрольной вершины и от неё до финиша. На каждом участке выберем кратчайший путь. Искомая длина равна d(11, 53) + d(53, 97).

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

  1. Сохраним граф списками исходящих рёбер, а веса — целыми десятыми долями.
  2. Напишем shortest(v, target): кратчайшее расстояние от v до выбранной цели.
  3. Для v == target вернём ноль; для недостижимой цели — None. В остальных случаях выберем минимум w + shortest(u, target).
  4. Сложим оба расстояния и только затем выполним // 10.

Цель входит в ключ кеша: продолжения до 53 и до 97 — разные подзадачи. Альтернативное решение хранит флаг «контрольная вершина уже посещена»; здесь разбиение на участки короче.

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

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

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

Ввод

11 53 2.7
53 97 1.8
11 97 0.9
11 80 0.6
80 53 1.2

Вывод

3
  1. Прямое ребро 11 → 97 имеет малый вес, но пропускает обязательную вершину.
  2. До 53 можно дойти напрямую за 2.7 или через 80 за 0.6 + 1.2 = 1.8.
  3. От 53 до финиша расстояние 1.8. Полная длина 1.8 + 1.8 = 3.6, выводим 3. Сумма целых частей участков дала бы другое число.

Код на Python и C++

Оба слагаемых существуют по гарантии условия. Функция возвращает расстояние в десятых долях; target включён в аргументы и тем самым в ключ кеша.

В C++ ключ словаря memo — пара {v, target}, вместо None — NO_PATH = -1, вместо // 10 — / 10.

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 == 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 == 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;
}

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

  • Игнорировать контрольную вершину

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

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

    Отдельные дробные части складываются и могут добавить целую единицу. Делите на десять после суммирования обоих участков.

  • Кешировать только номер вершины

    Ответ зависит и от цели. Если одна функция работает с несколькими целями, цель должна быть аргументом, либо кеш надо пересоздать.

  • Подменять порядок зависимостей нумерацией

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