【华为OD机试真题 python】最长广播效应

• 某通信网络中有N个网络结点，用1到N进行标识。
• 网络中的结点互联互通，且结点之间的消息传递有时延，相连结点的时延均为一个时间单位。
• 现给定网络结点的连接关系link[i]={u，v}，其中u和v表示网络结点。
• 当指定一个结点向其他结点进行广播，所有被广播结点收到消息后都会在原路径上回复一条响应消息，请计算发送结点至少需要等待几个时间单位才能收到所有被广播结点的响应消息。

注：

1. N的取值范围为[1，100];
2. 连接关系link的长度不超过3000，且1 <= u,v <= N;
3. 网络中任意结点间均是可达的;

输入描述：

• 输入的第一行为两个正整数，分别表示网络结点的个数N，以及时延列表的长度T；
• 接下来的T行输入，表示结点间的连接关系列表；
• 最后一行的输入为一个正整数，表示指定的广播结点序号；

输出描述：

• 输出一个整数，表示发送结点接收到所有响应消息至少需要等待的时长。

示例

输入

5 7
1 4
2 1
2 3
2 4
3 4
3 5
4 5
2

输出

4

class Dijkstra:
    def __init__(self, graph, goal, start):
        self.graph = graph
        self.goal = goal
        self.open_list = {}
        # open_list初始化为一个空字典，keys为节点'1''2'...,values为distance即从'1'到该点的实际代价
        self.closed_list = {}
        # closed_list初始化为一个空字典，键和值与open_list相同
        self.open_list[start] = 0
        # 因为我们初始节点为'1'，并且'1'到'1'的值为0,将其传入open_list列表中
        self.parent = {start: None}
        # 初始父节点为字典型，初始键为'1'值为None，其中键是子节点，值是父节点
        self.min_dis = None
        # 初始最短路径长度为None

    def shortest_path(self):

        while True:
            if self.open_list is None:
                print('搜索失败， 结束！')
                break

            distance, min_node = min(zip(self.open_list.values(), self.open_list.keys()))  # 取出距离最小的节点
            self.open_list.pop(min_node)  # 将其从 open_list 中去除

            self.closed_list[min_node] = distance  # 将节点加入 closed_list 中

            if min_node == self.goal:  # 如果节点为终点
                self.min_dis = distance
                shortest_path = [self.goal]  # 记录从终点回溯的路径
                father_node = self.parent[self.goal]
                while father_node != start:
                    shortest_path.append(father_node)
                    father_node = self.parent[father_node]
                shortest_path.append(start)
                print(shortest_path[::-1])  # 逆序
                print(self.min_dis*2)
            for node in self.graph[min_node].keys():  # 遍历当前节点的邻接节点
                if node not in self.closed_list.keys():  # 邻接节点不在 closed_list 中
                    if node in self.open_list.keys():  # 如果节点在 open_list 中
                        if self.graph[min_node][node] + distance < self.open_list[node]:
                            self.open_list[node] = distance + self.graph[min_node][node]  # 更新节点的值
                            self.parent[node] = min_node  # 更新继承关系
                    else:  # 如果节点不在 open_list 中
                        self.open_list[node] = distance + self.graph[min_node][node]
                        # 计算节点的值，并加入 open_list 中
                        self.parent[node] = min_node  # 更新继承关系


if __name__ == '__main__':
    N, T = map(int, input().split())
    g = {}
    while T:
        n = input().split()
        g.setdefault(f'{n[0]}', {})[f"{n[1]}"] = 1
        T -= 1
    goal = str(N)
    start = input()
    dijk1 = Dijkstra(g, goal, start)