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

Дан ориентированный взвешенный граф без циклов. Каждая строка содержит начало ребра, его конец и вес. В задаче этой страницы нужно найти целую часть длины кратчайшего пути из вершины 1 в вершину 100. Путь существует; длина — сумма весов его рёбер.

«Ориентированный» означает, что ребро можно пройти только в указанную сторону. «Ациклический» — что, двигаясь по стрелкам, нельзя вернуться в уже пройденную вершину. Номера вершин при этом могут убывать: сами номера ничего не говорят о порядке вычислений.

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

Обозначим через shortest(v) длину кратчайшего продолжения из вершины v до финиша. На финише продолжать путь не нужно, поэтому shortest(100) = 0. Для любой другой вершины переберём её исходящие рёбра. Переход v → u даёт длину w + shortest(u); из достижимых продолжений выбираем минимум.

Если от вершины нет пути до финиша, возвращаем None. В частности, тупик не должен давать нулевую длину: иначе короткая тупиковая ветвь могла бы выиграть у настоящего пути.

  1. Прочитаем строки до конца ввода и соберём список исходящих рёбер для каждой вершины.
  2. Вычислим ответ рекурсией: сначала ответы соседей, затем ответ текущей вершины.
  3. Поставим @lru_cache(None), чтобы каждая вершина вычислялась один раз. Общие продолжения нескольких путей будут переиспользованы.
  4. Возьмём целую часть только после получения полной длины.

Веса в нашей задаче имеют ровно одну цифру после точки. Удобно хранить их в десятых долях: 2.7 превращается в 27, без промежуточного float. Тогда сумма точна, а целая часть получается делением // 10. Отбрасывать дробную часть каждого ребра отдельно нельзя.

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

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

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

Ввод

1 70 1.8
70 20 0.6
20 100 2.1
1 100 6.4
1 9 0.1

Вывод

4
  1. У финиша shortest(100) = 0. Из вершины 20 до него остаётся 2.1.
  2. Из 70 остаётся 0.6 + 2.1 = 2.7. Уменьшение номера 70 → 20 не мешает рекурсии.
  3. Вершина 9 — тупик: её результат None, эту ветвь пропускаем.
  4. Из старта сравниваем прямой путь длины 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)
#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<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.

  • Перебирать все пути без запоминания

    Даже в небольшом графе путей может быть очень много. Кешируйте результат вершины; не храните и не перебирайте все полные последовательности.

  • Округлять каждое ребро

    Сначала сложите точные веса. Сумма целых частей отдельных весов может отличаться от целой части суммы.