代码随想录算法训练营 Day 52
Published:
Q1. KamaCoder 94
SPFA算法：使用队列优化的Bellman_ford算法
真正有效的计算是从当前节点出发能够直接到达的节点（即两边之间有边相连）
from collections import deque, defaultdict
if __name__ == '__main__':
n, m = map(int, input().split())
edges = defaultdict(list)
for _ in range(m):
s, t, v = map(int, input().split())
edges[s].append((t, v))
min_dist = [float('inf')] * (n + 1)
min_dist[1] = 0
queue = deque([1])
# 使用数组判断节点是否已经在队列中，避免多次加入
is_in_queue = [False] * (n + 1)
is_in_queue[1] = True
while queue:
node = queue.popleft()
is_in_queue[node] = False
for dest, weight in edges[node]:
if min_dist[node] != float('inf') and min_dist[dest] > min_dist[node] + weight:
min_dist[dest] = min_dist[node] + weight
if not is_in_queue[dest]:
queue.append(dest)
is_in_queue[dest] = True
print(min_dist[-1] if min_dist[-1] != float('inf') else 'unconnected')
Q2. KamaCoder 95
使用Bellman_ford算法，存在负权回路时，当遍历n次后，最短路径依然会有更新
if __name__ == '__main__':
n, m = map(int, input().split())
edges = []
for _ in range(m):
s, t, v = map(int, input().split())
edges.append([s, t, v])
min_dist = [float('inf')] * (n + 1)
min_dist[1] = 0
flag = False
for i in range(1, n + 1):
for src, dest, weight in edges:
if i < n:
if min_dist[src] != float('inf') and min_dist[dest] > weight + min_dist[src]:
min_dist[dest] = weight + min_dist[src]
else:
if min_dist[src] != float('inf') and min_dist[dest] > weight + min_dist[src]:
flag = True
if flag:
print('circle')
elif min_dist[-1] == float('inf'):
print('unconnected')
else:
print(min_dist[-1])
SPFA算法：在无负权环的情况下同一个节点最多只能加入$n-1$次队列
from collections import deque, defaultdict
if __name__ == '__main__':
n, m = map(int, input().split())
edges = defaultdict(list)
for _ in range(m):
s, t, v = map(int, input().split())
edges[s].append((t, v))
min_dist = [float('inf')] * (n + 1)
count = [0] * (n + 1)
min_dist[1] = 0
count[1] += 1
queue = deque([1])
flag = False
while queue:
curr = queue.popleft()
for dest, weight in edges[curr]:
if min_dist[curr] != float('inf') and min_dist[dest] > weight + min_dist[curr]:
min_dist[dest] = weight + min_dist[curr]
queue.append(dest)
count[dest] += 1
if count[dest] == n:
flag = True
while queue:
queue.popleft()
break
if flag:
print('circle')
elif min_dist[-1] == float('inf'):
print('unconnected')
else:
print(min_dist[-1])
Q3. KamaCoder 96
理解为什么需要将数组复制一次
if __name__ == '__main__':
n, m = map(int, input().split())
edges = []
for _ in range(m):
s, t, v = map(int, input().split())
edges.append([s, t, v])
src, dst, k = map(int, input().split())
min_dist = [float('inf')] * (n + 1)
min_dist[src] = 0
for _ in range(k + 1):
prev_min_dist = min_dist[:]
for s, d, w in edges:
if prev_min_dist[s] != float('inf') and min_dist[d] > prev_min_dist[s] + w:
min_dist[d] = prev_min_dist[s] + w
if min_dist[dst] == float('inf'):
print('unreachable')
else:
print(min_dist[dst])
SPFA算法，注意其中的优化策略，每次大循环，同一个节点只可能被加入一次队列
from collections import deque, defaultdict
if __name__ == '__main__':
n, m = map(int, input().split())
edges = defaultdict(list)
for _ in range(m):
s, t, v = map(int, input().split())
edges[s].append((t, v))
src, dst, k = map(int, input().split())
min_dist = [float('inf')] * (n + 1)
min_dist[src] = 0
queue = deque([src])
while queue and k >= 0:
visited = [False] * (n + 1)
prev_min_dist = min_dist[:]
for _ in range(len(queue)):
s = queue.popleft()
for d, w in edges[s]:
if min_dist[d] > prev_min_dist[s] + w:
min_dist[d] = prev_min_dist[s] + w
if not visited[d]:
queue.append(d)
visited[d] = True
k -= 1
if min_dist[dst] == float('inf'):
print('unreachable')
else:
print(min_dist[dst])