Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313076
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером $1$ в вершину с номером $100$. Существование хотя бы одного такого пути гарантируется. Под длиной кратчайшего пути понимается минимальная сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. $L ≤ 1000, M ≤ 1000; W ≤ 10 000$. Количество строк в файле не превосходит $200$. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Типовой пример организации данных во входном файле для графа на рисунке
| 100 6 6 1 7 4 1 1 | 12 7 1 7 100 100 100 4 | 1.0 7.0 1.0 5.5 2.0 8.0 12.0 2.5 |
Для приведённого примера при условии «не через вершину $7$» верным ответом будет $10$: из оставшихся путей $1–100$ (длина $12,0$) и $1–4–100$ (длина $10,5$) кратчайший имеет длину $10,5$.
Запрещённая вершина $M$ «вырезается» из графа: как только рекурсия попадает в $M$, возвращаем $+∞$ — «пути нет». Всё остальное — базовая рекурсия для кратчайшего пути. Проверка запрета обязана стоять раньше проверки $v == 100$, чтобы формулировка с $M = 100$ не ломала программу.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список (сосед, вес)
for line in open('23_7.txt'):
s = line.split() # любые пробелы и табуляции
if len(s) < 3: # пустая строка
continue
a, b, w = int(s[0]), int(s[1]), float(s[2])
g.setdefault(a, []).append((b, w))
M = 330
@lru_cache(None)
def f(v): # кратчайший путь v -> 100, минуя M
if v == M: # запрещённая вершина: пути нет
return float('inf')
if v == 100:
return 0
best = float('inf')
for u, w in g.get(v, []):
best = min(best, w + f(u))
return best
print(int(f(1)))Второй способ — не читать рёбра, инцидентные $M$ (дальше — обычная программа для кратчайшего пути):
M = 330
g = {}
for line in open('23_7.txt'):
s = line.split()
if len(s) < 3:
continue
a, b, w = int(s[0]), int(s[1]), float(s[2])
if a == M or b == M: # рёбра запрещённой вершины не читаем
continue
g.setdefault(a, []).append((b, w))Длина $14631,7$; путь $1 → 921 → 413 → 675 → 627 → 350 → 682 → 100$. Безусловный кратчайший путь $1 → 330 → 37 → 826 → 86 → 682 → 100$ имеет длину $12718,2$ и проходит через $330$.
20
