реши задачу по информатике, написав программу на питоне Берляндия — это страна, состоящая из n городов. Дорожную сеть Берляндии можно представить в виде взвешенного дерева, то есть всего в стране n − 1 дорога (обозначим города, которые соединяет i -я дорога за v i , u i и её вес за w i ), и от любого города можно добраться до любого другого ровно по одному пути, если не посещать никакой город дважды. Назовём город u достижимым из города v , если на единственном простом пути из

Для решения данной задачи, нужно написать программу на Python, которая будет находить все достижимые города из заданного города.

1. Сначала необходимо создать класс Node для представления города. В классе Node будут храниться идентификатор города и его соседи.

“`python
class Node:
def __init__(self, id):
self.id = id
self.neighbors = []
“`

2. Затем создадим функцию add_edge, которая будет добавлять дорогу (ребро) между двумя городами.

“`python
def add_edge(nodes, u, v, weight):
nodes[u].neighbors.append((v, weight))
nodes[v].neighbors.append((u, weight))
“`

3. Теперь напишем функцию find_reachable_cities, которая будет находить все достижимые города из заданного города. Для решения этой задачи мы будем использовать алгоритм обхода в глубину (DFS).

“`python
def find_reachable_cities(nodes, start_city, visited):
visited[start_city] = True

for neighbor in nodes[start_city].neighbors:
if not visited[neighbor[0]]:
find_reachable_cities(nodes, neighbor[0], visited)
“`

4. Наконец, напишем основную программу, в которой создадим все города и выполнятся вызов функции find_reachable_cities:

“`python
n = int(input(“Введите количество городов: “))

nodes = []
for i in range(n):
nodes.append(Node(i))

for i in range(n – 1):
u, v, weight = map(int, input(“Введите города и вес дороги через пробел: “).split())
add_edge(nodes, u, v, weight)

start_city = int(input(“Введите начальный город: “))

visited = [False] * n
find_reachable_cities(nodes, start_city, visited)

reachable_cities = []
for i in range(n):
if visited[i]:
reachable_cities.append(i)

print(“Достижимые города из”, start_city, “:”, reachable_cities)
“`

Эта программа сначала запрашивает количество городов, а затем поочередно запрашивает города и их дороги. Затем программа запрашивает начальный город и печатает все достижимые города.