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

Найдите путь из 11 в 97 с наибольшей суммой весов и выведите целую часть этой суммы. Граф ориентированный, без циклов; путь до заданного финиша существует.

Здесь важно слово «до финиша». Длинная ветвь, которая заканчивается в другой вершине, не является решением. Также максимальная сумма весов не обязательно достигается на пути с наибольшим числом рёбер.

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

Пусть longest(v) — наибольшая длина продолжения из v до 97. Для финиша значение равно нулю. Для другой вершины перебираем рёбра v → u и выбираем максимум из w + longest(u), но только если продолжение от u до финиша существует.

Недостижимость обозначим None. Начинать лучший результат с нуля опасно: тогда вершина в тупике выглядит как допустимый конец пути. Большое ребро в такой тупик может дать ложный максимум.

  1. Прочитаем граф и переведём веса в целые десятые доли.
  2. В рекурсии вернём ноль только на заданном финише.
  3. Пропустим все продолжения со значением None, из остальных выберем максимум.
  4. Запомним ответ каждой вершины и выведем целую часть итоговой суммы.

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

Линейная динамика здесь возможна благодаря отсутствию циклов. Этот код нельзя без изменений переносить на произвольный граф с циклами. В данных условиях время — O(V + E), память — O(V + E).

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

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

Ввод

11 97 4.2
11 80 1.1
80 20 1.4
20 97 1.2
11 9 90.0

Вывод

4
  1. У финиша значение ноль. Через 20 до него остаётся 1.2, через 80 — 1.4 + 1.2 = 2.6.
  2. Из старта сравниваем прямой путь длины 4.2 и путь с несколькими рёбрами длины 1.1 + 2.6 = 3.7.
  3. Ветвь в 9 имеет большой вес, но не достигает финиша. Её исключаем. Наибольшая допустимая длина — 4.2, целая часть — 4.

Код на Python и C++

Знак сравнения при выборе лучшего результата — >. Значение None отделяет недостижимый финиш от пути нулевой длины.

В C++ недостижимость обозначена NO_PATH = -1. Такие продолжения пропускаются до сравнения, поэтому минус единица не может победить настоящий путь.

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 longest(v):
    if v == 97:
        return 0
    best = None
    for u, w in graph.get(v, []):
        tail = longest(u)
        if tail is not None:
            candidate = w + tail
            if best is None or candidate > best:
                best = candidate
    return best


print(longest(11) // 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 longest(int v) {
    if (v == 97)
        return 0;
    if (memo.count(v))
        return memo[v];
    long long best = NO_PATH;
    for (auto [u, w] : graph[v]) {
        long long tail = longest(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 << longest(11) / 10 << endl;
}

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

  • Оставить минимум от шаблона кратчайшего пути

    Все переходы остаются похожими, но операция выбора меняется. Проверьте знак сравнения и смысл возвращаемой величины.

  • Принимать любой тупик за финиш

    Путь должен заканчиваться именно в заданной вершине. Большой вес ветви не делает её допустимой.

  • Максимизировать число переходов

    Веса могут различаться. Сравнивайте суммы весов, если условие спрашивает длину взвешенного пути.

  • Отбрасывать дробные части рёбер

    Целая часть суммы вычисляется после выбора полного пути. Округление рёбер меняет сравниваемые длины.