853. 有边数限制的最短路
摘要
Title: 853. 有边数限制的最短路
Tag: Bellman-ford、最短路
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
853. 有边数限制的最短路
-
题意
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。 -
思路
有边数限制的最短路只能用Bellman-ford来做
外层迭代n次的含义？
迭代了k次，代表从起点经过不少于k条边的走到每个点的最短距离为什么不少于？
因为有可能发生串联，即刚更新完b，又拿b去更新别的点，这样一次迭代可以更新两条边如何实现有边数限制？
实现一个备份数组，每次是从备份数组中的数去更新，保证不是实时更新可以发现，最外层迭代n次，每次迭代时，都需要全部遍历m条边。但其实当只有dist[u]变了的时候，我们才有必要更新dist[v]，如果dist[u]没变，就不必更新dist[v]，spfa正是省掉了这一操作
-
代码
平时写的时候不用加备份数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46'''
Author: NEFU AB-IN
Date: 2022-03-04 14:01:18
FilePath: \ACM\Acwing\853.py
LastEditTime: 2022-03-04 14:49:56
'''
from copy import deepcopy
N = 550
INF = int(2e9)
class Edge():
def __init__(self, u, v, w):
self.u = u
self.v = v
self.w = w
dist = [INF] * N
def bellman_ford():
dist[1] = 0
for i in range(k): #迭代k次
backup = deepcopy(dist)
for j in range(m): #遍历m条边
u, v, w = lst[j].u, lst[j].v, lst[j].w
dist[v] = min(dist[v], backup[u] + w) #用backup数组更新
if dist[n] > INF // 2:
return INF
return dist[n]
lst = []
n, m, k = map(int, input().split())
for i in range(m):
u, v, w = map(int, input().split())
lst.append(Edge(u, v, w))
res = bellman_ford()
if res == INF:
print("impossible")
else:
print(res)
