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

Из 11 в 97 нужно выбрать кратчайший путь. Если кратчайших путей несколько, среди них выбирается путь с наименьшим числом рёбер. Вывести требуется только это число рёбер.

Главный критерий — полная сумма весов, второй применяется лишь при точном равенстве длин. Граф ориентированный и ациклический, путь существует. Одна цифра после точки позволяет сравнивать длины точно в целых десятых долях.

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

Для каждой вершины будем хранить пару (distance, edges): длину лучшего продолжения и число рёбер в нём. На финише пара равна (0, 0). Если продолжения нет, возвращаем None.

Переход по ребру веса w к ответу (d, k) даёт пару (w + d, k + 1). Сравниваем такие пары обычным знаком <. Python сначала сравнивает первые элементы, а при их равенстве — вторые. Это и есть нужный порядок критериев.

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

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

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

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

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

Ввод

11 97 3.7
11 60 0.8
60 97 0.8
11 80 0.1
80 20 0.2
20 97 1.3

Вывод

2
  1. Прямой путь даёт пару (37, 1) в десятых долях.
  2. Путь через 60 имеет длину 0.8 + 0.8 = 1.6 и два ребра: пара (16, 2).
  3. Путь через 80, 20 имеет ту же длину 0.1 + 0.2 + 1.3 = 1.6, но три ребра: пара (16, 3).
  4. Минимальна пара (16, 2). Выводим только 2, а не длину пути.

Код на Python и C++

Первая координата пары хранит длину в десятых долях. Деление здесь не требуется: по условию выводится вторая координата — количество рёбер.

В C++ пара — pair<long long, int>. Знак < сравнивает пары так же, как в Python: сначала первые элементы, при равенстве вторые.

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


print(best_path(11)[1])
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
using namespace std;

const pair<long long, int> NO_PATH = {-1, -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, pair<long long, int>> memo;

pair<long long, int> best_path(int v) {
    if (v == 97)
        return {0, 0};
    if (memo.count(v))
        return memo[v];
    pair<long long, int> best = NO_PATH;
    for (auto [u, w] : graph[v]) {
        pair<long long, int> tail = best_path(u);
        if (tail != NO_PATH) {
            pair<long long, int> candidate = {w + tail.first, 1 + tail.second};
            if (best == NO_PATH || candidate < best)
                best = candidate;
        }
    }
    return memo[v] = best;
}

int main() {
    read_graph();
    cout << best_path(11).second << endl;
}

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

  • Поставить число рёбер первым критерием

    Пара (edges, distance) сначала выбирает самый короткий путь по числу шагов. Это другая задача: порядок элементов важен.

  • При равной длине выбрать больше рёбер

    Второй критерий тоже минимизируется. Обычное сравнение пар автоматически учитывает нужное направление обоих критериев.

  • Сравнивать целые части длин

    Разные полные длины могут иметь одинаковую целую часть. Сначала сравнивайте точные суммы, а не их округления.

  • Сравнивать равные суммы через float

    Разные способы сложения десятичных дробей могут дать небольшую двоичную погрешность. Целые десятые доли сохраняют точное равенство без подбора допуска.

  • Вывести длину вместо числа рёбер

    Длина нужна для выбора. В ответе требуется только второй элемент найденной пары.