Что спрашивают
Дан ориентированный взвешенный граф без циклов. Каждая строка содержит начало ребра, его конец и вес. В задаче этой страницы нужно найти целую часть длины кратчайшего пути из вершины 1 в вершину 100. Путь существует; длина — сумма весов его рёбер.
«Ориентированный» означает, что ребро можно пройти только в указанную сторону. «Ациклический» — что, двигаясь по стрелкам, нельзя вернуться в уже пройденную вершину. Номера вершин при этом могут убывать: сами номера ничего не говорят о порядке вычислений.
Приём решения
Обозначим через shortest(v) длину кратчайшего продолжения из вершины v до финиша. На финише продолжать путь не нужно, поэтому shortest(100) = 0. Для любой другой вершины переберём её исходящие рёбра. Переход v → u даёт длину w + shortest(u); из достижимых продолжений выбираем минимум.
Если от вершины нет пути до финиша, возвращаем None. В частности, тупик не должен давать нулевую длину: иначе короткая тупиковая ветвь могла бы выиграть у настоящего пути.
- Прочитаем строки до конца ввода и соберём список исходящих рёбер для каждой вершины.
- Вычислим ответ рекурсией: сначала ответы соседей, затем ответ текущей вершины.
- Поставим
@lru_cache(None), чтобы каждая вершина вычислялась один раз. Общие продолжения нескольких путей будут переиспользованы. - Возьмём целую часть только после получения полной длины.
Веса в нашей задаче имеют ровно одну цифру после точки. Удобно хранить их в десятых долях: 2.7 превращается в 27, без промежуточного float. Тогда сумма точна, а целая часть получается делением // 10. Отбрасывать дробную часть каждого ребра отдельно нельзя.
Корректность следует из первого ребра пути: любой путь начинается одним из перебираемых переходов, а лучшее продолжение уже найдено рекурсией. Циклов нет, поэтому зависимости заканчиваются. Время — O(V + E), память графа и кеша — O(V + E), где V — число вершин, E — число рёбер.
Разбор на примере
Ввод
1 70 1.8 70 20 0.6 20 100 2.1 1 100 6.4 1 9 0.1
Вывод
4
- У финиша
shortest(100) = 0. Из вершины20до него остаётся2.1. - Из
70остаётся0.6 + 2.1 = 2.7. Уменьшение номера70 → 20не мешает рекурсии. - Вершина
9— тупик: её результатNone, эту ветвь пропускаем. - Из старта сравниваем прямой путь длины
6.4и путь через70, 20длины1.8 + 2.7 = 4.5. Его целая часть —4.
Код на Python и C++
Код рассчитан на условия связанной задачи: граф без циклов, одна цифра после точки и существующий путь. Чтение идёт из стандартного ввода до конца файла; первой строки с числом рёбер нет.
В C++ уже найденные длины путей хранит словарь memo типа map<int, long long>: перед вычислением функция проверяет, нет ли там уже этой вершины. Вместо 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):
if v == 100:
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(1) // 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<int, long long> memo;
long long shortest(int v) {
if (v == 100)
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(1) / 10 << endl;
}
Типичные ошибки
- Перебирать вершины по номеру
Сортировка номеров не является топологическим порядком. Ребро из большей вершины в меньшую допустимо; рекурсия сама соблюдает зависимости.
- Выбирать путь с меньшим числом рёбер
Одно тяжёлое ребро может быть длиннее нескольких лёгких. Обычный обход в ширину минимизирует число переходов, а здесь нужна сумма весов.
- Считать тупик финишем
Ноль возвращается только для заданного финиша. В другой вершине без подходящего продолжения возвращается
None. - Перебирать все пути без запоминания
Даже в небольшом графе путей может быть очень много. Кешируйте результат вершины; не храните и не перебирайте все полные последовательности.
- Округлять каждое ребро
Сначала сложите точные веса. Сумма целых частей отдельных весов может отличаться от целой части суммы.