Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313298
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($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 |
Для приведённого примера для пары вершин $1$ и $100$ верным ответом будет $0$: путь $1–100$ с бесплатным ребром имеет длину $0$. Для пары вершин $6$ и $12$ ответом было бы $2$: путь $6–1–100–12$ с бесплатным ребром $1–100$ имеет длину $1,0 + 0 + 1,0 = 2,0,$ хотя без этого правила кратчайшим был бы другой путь — $6–1–7–100–12$ длиной $9,5$.
К состоянию рекурсии добавляется флаг: $f(v, free)$ — кратчайший путь из $v$ в $100$, если бонус ещё доступен ($free = 1$) или уже потрачен ($free = 0$). Из $v$ по ребру $v → u$ можно либо заплатить $w$ и сохранить флаг, либо, если флаг ещё есть, пройти бесплатно и продолжить уже с $free = 0$. Ответ $f(1, 1)$; $f(v, 0)$ — это обычная функция кратчайшего пути. Важно, что при бесплатном проходе флаг сбрасывается — иначе бонус будет использован на каждом ребре.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список (сосед, вес)
for line in open('23_23.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))
@lru_cache(None)
def f(v, free): # free = 1: бонус ещё не использован
if v == 100:
return 0
best = float('inf')
for u, w in g.get(v, []):
best = min(best, w + f(u, free)) # платим за ребро v -> u
if free:
best = min(best, f(u, 0)) # ребро бесплатно, бонус потрачен
return best
print(int(f(1, 1)))Второй способ — перебрать, какое ребро сделать бесплатным: путь через бесплатное ребро $a → b$ стоит $d(1, a) + d(b, 100)$. Расстояния от $1$ даёт один запуск алгоритма Дейкстры, расстояния до $100$ — обычная рекурсия:
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
import heapq
g = {} # вершина -> список (сосед, вес)
for line in open('23_23.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))
g.setdefault(b, [])
d1 = {v: float('inf') for v in g} # Дейкстра: расстояния от 1
d1[1] = 0
q = [(0, 1)]
while q:
dv, v = heapq.heappop(q)
if dv > d1[v]:
continue
for u, w in g[v]:
if dv + w < d1[u]:
d1[u] = dv + w
heapq.heappush(q, (d1[u], u))
@lru_cache(None)
def to100(v): # кратчайший путь v -> 100
if v == 100:
return 0
return min([w + to100(u) for u, w in g[v]], default=float('inf'))
best = to100(1) # бонусом можно и не пользоваться
for a in g:
for b, w in g[a]: # бесплатное ребро a -> b
best = min(best, d1[a] + to100(b))
print(int(best))Оптимальный путь $1 → 856 → 461 → 819 → 100$ с бесплатным ребром $1 → 856$ (вес $8619,5$) имеет длину $4317,7$. Обычный кратчайший путь $1 → 842 → 141 → 881 → 420 → 545 → 100$ имеет длину $12632,7$, а если сделать бесплатным самое тяжёлое его ребро, получится $9511,0$ — хуже.
20
