【洛谷】P1342 请柬（正反建图+dijkstra）

**洛谷 P1342请柬**

**题目描述**

在一个名叫"请柬"的城市里，住着很多人。每个人都有自己的朋友圈子，每个朋友圈子又有自己的朋友圈子...... 这样的链式结构可以一直延伸下去。现在，我们需要找到从某一个人出发到达另一个人所需的最短路径。

**正反建图**

首先，我们需要建立一个图来表示这个问题。我们可以使用邻接矩阵或邻接列表来实现。但是，由于链式结构的特点，这个图可能会非常大，甚至无法存储在内存中。因此，我们选择使用反向建图的方法。

**反向建图**

反向建图是一种将原来的图转置为另一个图的过程。在原来的图中，每条边都有一个方向，而在反向建图中，每条边都有相反的方向。这样做可以使我们更容易地找到从某一个人出发到达另一个人所需的最短路径。

**Dijkstra 算法**

现在，我们需要使用 Dijkstra 算法来找到从某一个人出发到达另一个人所需的最短路径。Dijkstra 算法是一种用于求解单源最短路径问题的算法，它可以保证找到最短的路径。

**代码实现**

import sysdef dijkstra(graph, start):
 """
 Dijkstra 算法，求解从某一个人出发到达另一个人所需的最短路径。
 Args:
 graph (dict): 反向建图，表示每个人之间的关系。
 start (int): 起始点。
 Returns:
 dict: 每个人到起始点的距离。
 """
 # 初始化距离为无穷大 distance = {i: float('inf') for i in graph}
 distance[start] =0 # 初始化未访问过的节点集合 unvisited = set(graph.keys())
 while unvisited:
 # 找到当前最短路径的起始点 current_node = min(unvisited, key=lambda x: distance[x])
 # 移除当前点 unvisited.remove(current_node)
 # 更新距离 for neighbor in graph[current_node]:
 new_distance = distance[current_node] +1 if new_distance < distance[neighbor]:
 distance[neighbor] = new_distance return distancedef main():
 """
 主函数。
 Returns:
 None """
 # 反向建图 graph = {
 'A': ['B', 'C'],
 'B': ['D'],
 'C': ['E'],
 'D': [],
 'E': []
 }
 # 起始点 start = 'A'
 # 执行 Dijkstra 算法 distance = dijkstra(graph, start)
 # 输出结果 print("从 {} 出发到达每个人所需的最短路径:".format(start))
 for person, dist in distance.items():
 print("{}: {}".format(person, dist))

if __name__ == "__main__":
 main()