代码随想录算法训练营day58| 117.软件构建 47.参加科学大会

# 拓扑排序：将关系转换为有向图，线性排序（如果有环，循环依赖则不行）
# 具体思路：统计每个节点的入度和出度；如果入度为0而有入度则为根；
# 依次删除入度为0的点，记住要更新剩下节点的入度，都会-1

from collections import deque, defaultdict

def topological_sort(n, edges):
    # 构造一个记录节点入度的列表，初始设置为0
    inDegree = [0]*n
    # 记录节点间的依赖关系
    umap = defaultdict(list)  # 每个键的默认值都是空列表[]
    
    # 构建图和入度表(s有多少个下一级)，s->t，则t的入度+1
    for s, t in edges:
        inDegree[t] += 1
        umap[s].append(t)
    
    # 初始化队列，加入所有入度为0的节点，再一个一个处理
    queue = deque([i for i in range(n) if inDegree[i]==0])
    result = []
    
    while queue:
        cur = queue.popleft()
        result.append(cur)   # 把第一个根加入结果中，并讨论删除这个节点后其他节点的入度变化情况
        for file in umap[cur]:
            inDegree[file] -= 1
            if inDegree[file] == 0:   # 当出现新的根，及时加入队列中
                queue.append(file)
    
    if len(result)==n:
        print(" ".join(map(str, result)))
    else:
        print(-1)


# 输入值
n, m = map(int, input().split())
edges = []
for _ in range(m):
    edges.append(list(map(int, input().split())))
topological_sort(n, edges)

# dijkstra算法，类似于prim
# 统计每个节点到源点的最小距离（minDist），和是否被访问过(visited)
# 找到距离源点最近的未访问过的节点，选中它；将它标记为访问过；更新minDist

def dijkstra(n, m, start, end):
    # 初始化邻接矩阵，每个节点到源点的距离都设置为无穷大，因为后面要保存最短距离
    grid = [[float('inf')]*(n+1) for _ in range(n+1)]
    for p1, p2, val in edges:
        grid[p1][p2] = val
    
    # 初始化距离数组，都为无穷大
    minDist = [float('inf')]*(n+1)
    minDist[start]=0  # 自己到自己的距离为0
    # 访问数组，初始为未访问
    visited = [False]*(n+1)
    
    # 遍历所有节点
    for _ in range(1, n+1):
        minVal = float('inf')
        cur = -1
        
        # 选择距离源点最近且未访问过的节点
        for v in range(1, n+1):
            if not visited[v] and minDist[v]<minVal:
                minVal = minDist[v]
                cur = v
        # 若节点都访问过，则提前结束
        if cur == -1:
            break
        # 标记该节点为被访问
        visited[cur] = True
        
        # 更新剩余未访问节点到源点的距离 ？？？？？ 真没看懂啊！！！！！
        for v in range(1, n+1):
            if not visited[v] and grid[cur][v] != float('inf') and minDist[cur]+grid[cur][v]<minDist[v]:
                minDist[v] = minDist[cur]+grid[cur][v]
    return -1 if minDist[end]==float('inf') else minDist[end]
    
# 输入值
n, m = map(int, input().split())
edges = []
for _ in range(m):
    edges.append(list(map(int, input().split())))
start = 1
end = n
result = dijkstra(n, m, start, end)
print(result)