代码随想录算法训练营 Day 50
Published:
Q1. KamaCoder 117
拓扑排序：给定一个有向图，将有向图转成线性的排序。拓扑排序也常用来判断有向图中是否无环
创建队列，每次都找入度为0的点，将其加入到结果集中，并从图中删除（即减少邻居节点的入度）。如果最后结果集长度与节点总数一致，则表示没有环的存在
from collections import defaultdict, deque
if __name__ == '__main__':
n, m = map(int, input().split())
in_degree = [0] * n
dependancy = defaultdict(list)
for _ in range(m):
s, t = map(int, input().split())
dependancy[s].append(t)
in_degree[t] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
res = []
while queue:
curr_file = queue.popleft()
res.append(curr_file)
for file in dependancy[curr_file]:
in_degree[file] -= 1
if in_degree[file] == 0:
queue.append(file)
if len(res) == n:
print(' '.join(map(str, res)))
else:
print(-1)
Q2. KamaCoder 47
dijkstra最短路算法：起点到所有节点的最短路径，但路径权重不能有负数（数组中保存的是从起点出发的路径长度）
- 选择离起点最近且没有被访问过的节点
- 标记该节点，将其加入到最短路径中
- 更新未被访问过的节点到起点的最短距离
if __name__ == '__main__':
n, m = map(int, input().split())
path = [[float('inf')] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
s, e, v = map(int, input().split())
path[s][e] = v
min_dist = [float('inf')] * (n + 1)
visited = [False] * (n + 1)
min_dist[1] = 0
for _ in range(1, n + 1):
min_val = float('inf')
curr = -1
for v in range(1, n + 1):
if not visited[v] and min_dist[v] < min_val:
min_val = min_dist[v]
curr = v
if curr == -1:
break
visited[curr] = True
for v in range(1, n + 1):
if not visited[v] and path[curr][v] != float('inf') and min_dist[curr] + path[curr][v] < min_dist[v]:
min_dist[v] = min_dist[curr] + path[curr][v]
print(-1 if min_dist[-1] == float('inf') else min_dist[-1])