Что спрашивают
Нужно найти кратчайший путь из 11 в 97, который обязательно проходит через 53. Граф ориентированный, без циклов, веса положительные. Ответ — целая часть полной длины; существование подходящего пути гарантируется.
Обычный кратчайший путь может пройти мимо контрольной вершины. Поэтому недостаточно один раз решить задачу без ограничений и затем посмотреть, есть ли в найденном пути нужная вершина.
Приём решения
Любой допустимый путь делится в вершине 53 на два участка: от старта до контрольной вершины и от неё до финиша. На каждом участке выберем кратчайший путь. Искомая длина равна d(11, 53) + d(53, 97).
Почему участки можно выбрать независимо? Если они пересекутся в другой вершине, участок от неё до 53 и обратное продолжение образуют ориентированный цикл. В нашем графе циклов нет, поэтому соединение найденных участков остаётся допустимым путём.
- Сохраним граф списками исходящих рёбер, а веса — целыми десятыми долями.
- Напишем
shortest(v, target): кратчайшее расстояние отvдо выбранной цели. - Для
v == targetвернём ноль; для недостижимой цели —None. В остальных случаях выберем минимумw + shortest(u, target). - Сложим оба расстояния и только затем выполним
// 10.
Цель входит в ключ кеша: продолжения до 53 и до 97 — разные подзадачи. Альтернативное решение хранит флаг «контрольная вершина уже посещена»; здесь разбиение на участки короче.
Каждый путь обязан содержать оба участка, поэтому не может быть короче суммы их минимумов. Соединение кратчайших участков эту сумму достигает. Целей всего две, так что время и память остаются O(V + E).
Разбор на примере
Ввод
11 53 2.7 53 97 1.8 11 97 0.9 11 80 0.6 80 53 1.2
Вывод
3
- Прямое ребро
11 → 97имеет малый вес, но пропускает обязательную вершину. - До
53можно дойти напрямую за2.7или через80за0.6 + 1.2 = 1.8. - От
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)
<iostream>
<map>
<string>
<utility>
<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;
}
Типичные ошибки
- Игнорировать контрольную вершину
Минимум среди всех путей может быть меньше минимума среди разрешённых. Ограничение учитывается до выбора лучшего пути.
- Округлять участки перед сложением
Отдельные дробные части складываются и могут добавить целую единицу. Делите на десять после суммирования обоих участков.
- Кешировать только номер вершины
Ответ зависит и от цели. Если одна функция работает с несколькими целями, цель должна быть аргументом, либо кеш надо пересоздать.
- Подменять порядок зависимостей нумерацией
Контрольная вершина может иметь номер меньше предыдущей. Считайте по рёбрам графа, а не по возрастанию номеров.