本次題目來自于卡碼網
117. 軟件構建（拓撲排序）
python設置默認值
from collections import defaultdict
aa = defaultdict(int)拓撲排序：找到入度為0的節點，然后移除。如果最后都能移除，則無環，可以排序。
import collections
if __name__ == '__main__':n, m = map(int, input().strip().split())inDegree = [0] * n # 記錄每個文件的入度umap = collections.defaultdict(list) # 記錄文件依賴關系result = [] # 記錄結果for _ in range(m):s, t = map(int, input().strip().split())inDegree[t] += 1 # t的入度加一umap[s].append(t) # 記錄s指向哪些文件queue = collections.deque()for i in range(n):# 入度為0的文件，可以作為開頭，先加入隊列if inDegree[i] == 0:queue.append(i)while queue:cur = queue.popleft() # 當前選中的文件result.append(cur)files = umap[cur] # 獲取該文件指向的文件if files: # cur有后續文件for i in range(len(files)):inDegree[files[i]] -= 1 # cur的指向的文件入度-1if inDegree[files[i]] == 0:queue.append(files[i])if len(result) == n:print(" ".join([str(i) for i in result]))else:print(-1)47. 參加科學大會（dijkstra算法）
最短路是圖論中的經典問題即：給出一個有向圖，一個起點，一個終點，問起點到終點的最短路徑。
dijkstra算法：在有權圖（權值非負數）中求從起點到其他節點的最短路徑算法。
需要注意兩點：
- dijkstra 算法可以同時求 起點到所有節點的最短路徑
- 權值不能為負數
dijkstra算法和prim算法相似，都是分下面三步，但是變為了源點到節點的距離。
- 第一步，選源點到哪個節點近且該節點未被訪問過
- 第二步，該最近節點被標記訪問過
- 第三步，更新非訪問節點到源點的距離（即更新minDist數組）
if __name__ == '__main__':n, m = map(int, input().strip().split())grid = [[float('inf')] * (n + 1) for _ in range(n + 1)]for i in range(m):p1, p2, val = map(int, input().strip().split())grid[p1][p2] = valstart = 1end = n# 存儲從源點到每個節點的最短距離minDist = [float('inf')] * (n + 1)# 記錄頂點是否被訪問過visited = [False] * (n + 1)minDist[start] = 0 # 起始點到自身的距離為0for i in range(1, n + 1): # 遍歷所有節點minVal = float('inf')cur = 1# 1、選距離源點最近且未訪問過的節點for v in range(1, n + 1):if not visited[v] and minDist[v] < minVal:minVal = minDist[v]cur = vvisited[cur] = True # 2、標記該節點已被訪問# 3、第三步，更新非訪問節點到源點的距離（即更新minDist數組）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]if minDist[end] == float('inf'):print(-1) # 不能到達終點else:print(minDist[end]) # 到達終點最短路徑
