Карточки
Тесты
Главная
Курсы
Подписка
23. Алгоритмические задачи, связанные с анализом графов: #313233
В текстовом файле содержится описание ациклического ориентированного взвешенного графа.
В каждой строке файла записаны два натуральных числа ($L, M$) и одно положительное вещественное число ($W$). $L, M$ — номера вершин графа, $W$ — вес ребра, ведущего из вершины $L$ в вершину $M$. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите и запишите в ответе целую часть длины кратчайшего пути из вершины с номером $1$ в вершину с номером $100$, проходящего через обе вершины с номерами $187$ и $769$ (порядок, в котором путь проходит эти вершины, не задан). Существование хотя бы одного такого пути гарантируется. Под длиной пути понимается сумма весов рёбер, составляющих путь.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. $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$ пути, проходящего через обе вершины $7$ и $4$, не существует. Для пары вершин $6$ и $12$ при условии прохождения через вершины $1$ и $7$ верным ответом было бы $9$: единственный такой путь $6–1–7–100–12$ имеет длину $9,5$.
Путь через обе вершины $K$ и $M$ проходит их в каком-то порядке: либо $1 → K → M → 100$, либо $1 → M → K → 100$. Каждый вариант — сумма трёх кратчайших отрезков, как в задании $4$; в ациклическом графе не более одного из вариантов осуществим (если есть путь $K → M$, то пути $M → K$ нет), поэтому ответ — минимум из двух сумм, одна из которых равна $+∞$.
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
g = {} # вершина -> список (сосед, вес)
for line in open('23_19.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))
def short(src, dst): # длина кратчайшего пути src -> dst
@lru_cache(None)
def f(v):
if v == dst:
return 0
best = float('inf')
for u, w in g.get(v, []):
best = min(best, w + f(u))
return best
return f(src)
K, M = 187, 769
a = short(1, K) + short(K, M) + short(M, 100) # сначала K, потом M
b = short(1, M) + short(M, K) + short(K, 100) # сначала M, потом K
print(int(min(a, b))) # один из вариантов равен infВторой способ — три запуска алгоритма Дейкстры (из $1$, из $K$ и из $M$):
import heapq
g = {} # вершина -> список (сосед, вес)
for line in open('23_19.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, []) # все вершины — ключи словаря
def dijkstra(src): # расстояния от src до всех вершин
d = {v: float('inf') for v in g}
d[src] = 0
q = [(0, src)]
while q:
dv, v = heapq.heappop(q)
if dv > d[v]:
continue
for u, w in g[v]:
if dv + w < d[u]:
d[u] = dv + w
heapq.heappush(q, (d[u], u))
return d
K, M = 187, 769
d1, dK, dM = dijkstra(1), dijkstra(K), dijkstra(M)
print(int(min(d1[K] + dK[M] + dM[100], d1[M] + dM[K] + dK[100])))Верный порядок — сначала $769$, потом $187$; длина $24461,7$; путь $1 → 662 → 36 → 68 → 628 → 769 → 992 → 685 → 187 → 758 → 307 → 100$ ($11$ рёбер). Вариант «сначала $187$» невозможен: из $187$ вершина $769$ недостижима.
20
