今日专题：拓扑排序 迪杰斯特拉算法（有向图的最短路径）
117. 软件构建
思路：每次找入度为0的点，清除他和后续节点的关联（后续节点的入度-1）
总结：使用队列去处理度为0的节点（遍历它的后继节点，使他们的入度-1）
from collections import deque#每次循环找一个入度为0的点,把它加入到结果中，并且将其相邻点的关联去掉def main():n,m=map(int,input().split())edges=[0]*nnext=[[] for _ in range(n)]for _ in range(m):s,t=map(int,input().split())edges[t]+=1next[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]-=1if 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]=vvisited=set()mindest=[float('inf')]*(n+1)mindest[1]=0node=1visited.add(node)#最多选n次for _ in range(n):tempNode=0tempDest=mindest[0]for i in range(n+1):if i==node:continueif 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=jtempDest=mindest[j] node=tempNodevisited.add(node)res=-1 if mindest[-1]==float('inf') else mindest[-1]print(res)if __name__ =="__main__":main()
