Что спрашивают
Из 11 в 97 нужно выбрать кратчайший путь. Если кратчайших путей несколько, среди них выбирается путь с наименьшим числом рёбер. Вывести требуется только это число рёбер.
Главный критерий — полная сумма весов, второй применяется лишь при точном равенстве длин. Граф ориентированный и ациклический, путь существует. Одна цифра после точки позволяет сравнивать длины точно в целых десятых долях.
Приём решения
Для каждой вершины будем хранить пару (distance, edges): длину лучшего продолжения и число рёбер в нём. На финише пара равна (0, 0). Если продолжения нет, возвращаем None.
Переход по ребру веса w к ответу (d, k) даёт пару (w + d, k + 1). Сравниваем такие пары обычным знаком <. Python сначала сравнивает первые элементы, а при их равенстве — вторые. Это и есть нужный порядок критериев.
- Переведём веса в целые десятые доли, не используя
float. - Вычислим рекурсией лучшую пару каждого исходящего соседа.
- Добавим вес текущего ребра к первому элементу и единицу ко второму.
- Выберем минимальную пару и выведем её второй элемент для старта.
Хранить только число рёбер недостаточно: тогда можно предпочесть очень короткий по числу переходов, но тяжёлый путь. Округлять расстояния до сравнения тоже нельзя: разные длины могут иметь одинаковую целую часть. Здесь длина служит критерием выбора и не выводится.
Оптимальность сохраняется при добавлении одного и того же ребра: к сравниваемым длинам прибавляется одинаковый вес, к числам рёбер — одинаковая единица. Поэтому лучшее продолжение соседа достаточно для выбора пути из текущей вершины. Кеш по вершине даёт время и память O(V + E).
Разбор на примере
Ввод
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
- Прямой путь даёт пару
(37, 1)в десятых долях. - Путь через
60имеет длину0.8 + 0.8 = 1.6и два ребра: пара(16, 2). - Путь через
80, 20имеет ту же длину0.1 + 0.2 + 1.3 = 1.6, но три ребра: пара(16, 3). - Минимальна пара
(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])
<iostream>
<map>
<string>
<utility>
<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
Разные способы сложения десятичных дробей могут дать небольшую двоичную погрешность. Целые десятые доли сохраняют точное равенство без подбора допуска.
- Вывести длину вместо числа рёбер
Длина нужна для выбора. В ответе требуется только второй элемент найденной пары.