＜代码随想录＞ 算法训练营-2025.01.09

今日专题：拓扑排序 迪杰斯特拉算法（有向图的最短路径）

117. 软件构建

思路：每次找入度为0的点，清除他和后续节点的关联（后续节点的入度-1）
总结：使用队列去处理度为0的节点（遍历它的后继节点，使他们的入度-1）

from collections import deque

#每次循环找一个入度为0的点,把它加入到结果中，并且将其相邻点的关联去掉

def main():
    n,m=map(int,input().split())
    edges=[0]*n
    next=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        edges[t]+=1
        next[s].append(t)
    dq=deque()
    res=[]
    for i in range(n):
        if edges[i]==0:
            dq.append(i)
    while len(dq)>0:
        node=dq.popleft()
        res.append(node)
        for i in next[node]:
            edges[i]-=1
            if edges[i]==0:
                dq.append(i)
    print(' '.join(map(str,res)) if len(res)==n else -1)

if __name__=="__main__":
    main()

47. 参加科学大会（第六期模拟笔试）

思路：和prim算法类似，逐步更新最短路径
总结：选点是遍历mindest表，找到最短且没有访问过的点

#从一个节点出发，更新最短距离

def main():
    n,m=map(int,input().split())
    graph=[[-1]*(n+1) for _ in range(n+1)]
    for _ in range(m):
        s,e,v=map(int,input().split())
        graph[s][e]=v
    visited=set()
    mindest=[float('inf')]*(n+1)
    mindest[1]=0
    node=1
    visited.add(node)
    #最多选n次
    for _ in range(n):
        tempNode=0
        tempDest=mindest[0]
        for i in range(n+1):
            if i==node:
                continue
            if graph[node][i]!=-1 :
                mindest[i]=min(mindest[i],mindest[node]+graph[node][i])
            for j in range(n+1):
                if j not in visited:
                    if mindest[j]<tempDest:
                        tempNode=j
                        tempDest=mindest[j]        
        node=tempNode
        visited.add(node)
    res=-1 if mindest[-1]==float('inf') else mindest[-1]
    print(res)
            
        

if __name__ =="__main__":
    main()

原文地址：https://blog.csdn.net/qq_44849862/article/details/145061905

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！