Задача по информатике тема графы
Помогите решить задачу
Проще пареной репы, всех дел на 20 секунд:
4 километра.
Смотри сколько дорог в каждом пункте и куда они ведут:
П3 - Б (только из П3 и Б выходят 3 дороги)
П4 - Ж (только из П4 и Ж выходят 2 дороги)
П5 - Г (из Ж одна дорога ведет в Б, а вторая сюда, значит, это Г)
П6 - В (из Г две дороги ведут в уже известные Б и Ж, третья ведет в пункт П6, откуда выходят 4 дороги, значит, это В)
П7 - Е (четвертая дорога из Г ведет сюда, значит, это Е)
Г-Е = П5-П7 = 4
А вот А и Д однозначно определить нельзя. Либо П1=А, П2=Д, либо наоборот, П1=Д, П2=А
ответ: 4(решение ниже)
import heapq
graph = {
"P1": {"P6": 10}, "P2": {"P6": 12},
"P3": {"P4": 10, "P5": 9, "P6": 5},
"P4": {"P3": 10, "P5": 5}, "P5": {"P3": 9, "P4": 5, "P6": 8, "P7": 4},
"P6": {"P1": 10, "P2": 12, "P3": 5, "P5": 8}, "P7": {"P5": 4}
}
def dj(graph, s, e):
q, d = [(0, s)], {n: float('inf') for n in graph}
d[s] = 0
while q:
cd, n = heapq.heappop(q)
for nb, w in graph[n].items():
if (dist := cd + w) < d[nb]:
d[nb] = dist
heapq.heappush(q, (dist, nb))
return d[e]
print(dj(graph, "P5", "P7"))
Около каждой вершины расставляешь число путей выходящих из этой вершины. А-1, Б-3, В-4, Г-4, Д-1, Е-1, Ж-2. Замечаешь, что только из одной вершины выходят 2 пути и только из одной вершины выходят 3 пути. Смотришь таблицу. Видишь что в строке П3 стоят 3 числа. Значит П3 это вершина Б. Видишь что в строке П4 стоят 2 числа. Значит П4 это вершина Ж. Тебя интересует петь ГЕ. Из вершины Г выходят 4 пути. Смотришь таблицу. 4 числа стоят в строках П5 и П6. Значит П5 и П6 это вершины В и Г. Но нужно определить соответствие. Из вершины Г есть прямые пути в Б и Ж, а из вершины В нет прямого пути в Ж. Смотришь таблицу. Из П5 есть пути в П3 и П4, которые у нас Б и Ж соответственно. Из П6 есть путь в П3, но нет пути в П4. Значит П5 это Г, П6 это В. Из П5 остается единственный путь в П7. Это и есть Е. Из таблицы видишь, что он равен 4.
Ответ: 4.
Тебе решение или объяснить как решается
Я тут граф