题解 | #【模板】单源最短路Ⅰ ‖ 无权图#（Python3）

import heapq
import sys

input = sys.stdin.read  # 读取所有输入，适用于在线评测系统

INF = int(1e18)  # 定义一个无穷大的值，用于初始化距离数组
N = int(2e6 + 5)  # 定义数组的最大长度
dist = [INF] * N  # 初始化距离数组，所有节点的距离初始为无穷大
a = [[] for _ in range(N)]  # 初始化邻接表，用于存储图


def dijkstra(s):
    """使用Dijkstra算法计算单源最短路径
    参数:
    s -- 起始节点的索引
    """
    dist[s] = 0  # 起始节点的距离设置为0
    pq = [(0, s)]  # 创建一个优先队列，用于存储待处理的节点
    heapq.heapify(pq)  # 将列表转换为堆
    while pq:
        d, u = heapq.heappop(pq)  # 弹出堆顶元素，即当前距离最小的节点
        if d > dist[u]:  # 如果当前节点的距离已经被更新过，则跳过
            continue
        for v, w in a[u]:  # 遍历当前节点的所有邻接节点
            if dist[u] + w < dist[v]:  # 如果找到更短的路径
                dist[v] = dist[u] + w  # 更新距离
                heapq.heappush(pq, (dist[v], v))  # 将新节点加入堆中


def solve():
    """解决函数，读取输入数据，调用Dijkstra算法，并输出结果"""
    data = input().split()  # 读取所有输入并分割成列表
    index = 0
    n = int(data[index])  # 读取节点数量
    index += 1
    m = int(data[index])  # 读取边的数量
    index += 1
    s = int(data[index])  # 读取起始节点
    index += 1
    for _ in range(m):
        u = int(data[index])  # 读取边的起点
        index += 1
        v = int(data[index])  # 读取边的终点
        index += 1
        a[u].append((v, 1))  # 在邻接表中添加边
    dijkstra(s)  # 调用Dijkstra算法
    result = []
    for i in range(1, n + 1):  # 遍历所有节点，准备输出结果
        if dist[i] == INF:  # 如果节点不可达，输出-1
            result.append("-1")
        else:
            result.append(str(dist[i]))  # 否则输出距离
    print(" ".join(result))  # 打印结果


def main():
    """主函数，程序入口"""
    solve()  # 调用解决函数


if __name__ == "__main__":
    main()  # 如果是直接运行脚本，则调用主函数