本體考察的是拓撲排序的思路，對于所有的有向無環圖進行拓撲排序后輸出的長度一定是和原結點數相同的。整體思路是找到當前所有的入度為0的結點，添加到結果中，并且查看對應的后續結點將其入度減1，如果減完之后入度為0，那就也添加到待處理結點中，直到找不到符合條件的待處理結點。最后查看結果長度與結點數是否一致，一致的話輸出，不一致說明無法滿足條件。

import collections
N, M = map(int, input().split())
inDegree = [0] * N
umap = [[] for _ in range(N)]
for i in range(M):s, t = map(int, input().split())inDegree[t] += 1umap[s].append(t)
queue = collections.deque()
for i in range(N):if inDegree[i] == 0:queue.append(i)
result = []
while queue:cur = queue.popleft()result.append(cur)for file in umap[cur]:inDegree[file] -= 1if inDegree[file] == 0:queue.append(file)
if len(result) == N:print(' '.join(map(str, result)))
else:print(-1)

本題使用的是dijkstra算法，和prim基本一致，唯一不同的是minDist數組中存放的不是到每個結點到已經訪問結點的最小距離，而是距離源點的最小距離，別的都是一致的。

n, m = map(int, input().split())
grid = [[float('inf')] * (n+1) for _ in range(n+1)]
for i in range(m):s, t, v = map(int, input().split())grid[s][t] = v
start = 1
end = n 
visited = [False] * (n+1)
minDist = [float('inf')] * (n+1)
minDist[start] = 0
for i in range(n):minVal = float('inf')for i in range(1, n+1):if minDist[i] < minVal and not visited[i]:minVal = minDist[i]cur = i visited[cur] = Truefor i in range(1, n+1):if not visited[i] and grid[cur][i]!=float('inf') and minDist[cur]+grid[cur][i] < minDist[i]:minDist[i] = minDist[cur] + grid[cur][i]
if minDist[end] < float('inf'):print(minDist[end])
else:print(-1)