6 Шпаргалка по заданию 23
Шпаргалка по заданию 23
Способ 1 — Беллман–Форд
edges = []
for s in open("23.txt"):
a, b, w = s.split()
edges.append((int(a), int(b), float(w)))
INF = 10**10
dist = [INF] * 1001
dist[1] = 0 # старт
for _ in range(len(edges)):
for a, b, w in edges:
if dist[a] + w < dist[b]:
dist[b] = dist[a] + w
print(int(dist[100])) # финиш — вершина 100Способ 2 — рекурсия с запоминанием
from collections import defaultdict
from functools import lru_cache
d = defaultdict(list)
for s in open("23.txt"):
frm, to, w = [float(x) for x in s.split()]
d[frm].append([to, w])
@lru_cache(None)
def f(curr, end):
if curr == end: return 0
if curr not in d: return 10**8
return min(w + f(to, end) for to, w in d[curr])
print(int(f(1, 100))) # старт 1, финиш 100Что где менять
файл имя приложенного файла в open(...)
старт dist[1] = 0 (номер стартовой вершины)
финиш print(int(dist[100])) (номер конечной вершины)
целая часть int(...) отбрасывает дробную часть
вес — дробный float(w) (веса вещественные!)⚠️ Типичные ошибки 1. Прочитал вес как целое ( 2. Забыл поставить 3. Сделал слишком мало проходов. Надёжно — повторить по всем рёбрам 4. Взял маленький массив 5. Забыл про целую часть: в ответе — 6. Перепутал направление ребра: 7. В рекурсии забыл 8. В рекурсии перепутал базу: |
💡 Последнее напутствие Новое задание 23 решается коротким кодом — двумя способами на выбор. Беллман–Форд: поставил старту расстояние 0, много раз прошёлся по всем рёбрам, укорачивая пути, прочитал ответ у финиша. Рекурсия с запоминанием: длина пути = шаг по ребру плюс кратчайший путь дальше, а Не пугайся слов «граф» и «кратчайший путь»: любой из двух способов умещается в несколько строк и не ошибается. Бери тот, что понятнее именно тебе. Удачи на экзамене — Профиматика с тобой! |