【代码随想录算法训练营第六十三天|卡码网117.软件构造、47.参加科学大会】

117.软件构造

本体考察的是拓扑排序的思路，对于所有的有向无环图进行拓扑排序后输出的长度一定是和原结点数相同的。整体思路是找到当前所有的入度为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] += 1
    umap[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] -= 1
        if inDegree[file] == 0:
            queue.append(file)
if len(result) == N:
    print(' '.join(map(str, result)))
else:
    print(-1)

47.参加科学大会

本题使用的是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] = True
    for 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)