Что спрашивают
Нужно найти кратчайший путь из 11 в 97, содержащий ребро 53 → 29. Недостаточно отдельно посетить вершины 53 и 29: переход между ними должен быть именно этим ребром и именно в указанном направлении.
Граф ориентированный и ациклический, допустимый путь существует. Выводится целая часть его длины; вес каждого ребра записан с одной цифрой после точки.
Приём решения
Добавим к номеру вершины флаг used: пройдено ли обязательное ребро на пути от старта до текущего места. Функция shortest(v, used) возвращает минимальную длину ещё не пройденного участка до финиша при таком состоянии.
Для перехода v → u новый флаг равен used or (v, u) == (53, 29). После нужного ребра флаг остаётся истинным на всех последующих шагах. На финише возвращаем ноль только при истинном флаге, иначе None: прийти к финишу без выполнения условия нельзя.
- Соберём список исходящих рёбер с весами в десятых долях.
- Начнём вычисление из состояния
(11, False). - На каждом ребре обновим флаг, запросим лучшее продолжение и добавим вес перехода.
- Из всех допустимых продолжений выберем минимум. В конце разделим общую длину на десять.
У одной вершины могут быть два разных ответа: до прохождения обязательного ребра и после него. Именно поэтому флаг входит в аргументы кешируемой функции. Состояние описывает всю нужную предысторию; конкретный список уже пройденных вершин в графе без циклов хранить не нужно.
Каждый допустимый путь возникает среди переходов с нужным обновлением флага, а финиш отсекает все недопустимые. На вершину приходится не более двух состояний; время и память — O(V + E). Другой вариант решения — сложить расстояние до начала обязательного ребра, его вес и расстояние от его конца до финиша.
Разбор на примере
Ввод
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
- Прямое ребро
11 → 97приводит к финишу сused = Falseи отвергается. - Путь
11 → 53 → 80 → 29 → 97проходит через обе нужные вершины, но пропускает ребро53 → 29. Он тоже не подходит. - На разрешённом пути флаг меняется при переходе
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)
<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, 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, чтобы выполненное условие оставалось выполненным. - Запоминать ответ только по вершине
Разрешённые продолжения зависят от того, выполнено ли требование раньше. Ключ кеша должен включать этот флаг.