python使用广度优先搜索找最短路径之和

"""
修改我们在视频中学习的广度优先搜索算法，使用上一题构造的数据结构表示图，作为函数的一个输入。输出某个给定的顶点到其他的所有顶点最小距离的和。
"""
import queue as que

n = int(input())

graph = {}

for i in range(n):
    src, dst = input().split()
    src, dst = int(src), int(dst)
    # 对于每一条输入的连边 src -> dst 你需要按照题目要求作相应的处理
    # 得到正确的代表图的字典 graph

    if dst not in graph:
        graph[dst] = []

    if src in graph:
        graph[src].append(dst)
    else:
        graph[src] = [dst]

start = int(input())


def ShortestPath(graph, start):
    sum_of_minDist = 0

    # looked = dict()
    # for x in graph:
    #     looked[x] = [0] * len(graph[x])

    # for x in looked:
    #     print(x, looked[x])

    point_num = len(graph)
    # print('字典长度：', point_num)
    point_short_lens = [0] * (point_num+1)
    looked = [0] * (point_num + 1)
    looked[start] = 1
    # print('test', point_short_lens[7])
    # point_short_lens[start] = 0

    # print('长度', point_num)
    q = que.Queue(point_num)
    q.put(start)
    # 你需要正确的计算顶点 start 到图graph的其他顶点的距离最小值的和 sum_of_minDist

    while q.empty() is False:
        point = q.get()
        # print(point)

        for index in range(len(graph[point])):
            current_point = graph[point][index]
            # 没走过的
            if looked[current_point] == 0:
                looked[current_point] = 1
                q.put(current_point)
                # print('{}->{}'.format(point, graph[point][index]))
                point_short_lens[current_point] = point_short_lens[point] + 1
                # print('将{}的次数变为了{}'.format(current_point, point_short_lens[point] + 1))

    # print(point_short_lens)
    for short_distance in point_short_lens:
        sum_of_minDist += short_distance
    return sum_of_minDist


print(ShortestPath(graph, start))