2194出差-节点开销Bellman-ford/图论
题目网址： 蓝桥账户中央https://i-blog.csdnimg.cn/direct/ee50c986c759440381328f169546db67.png
我先用Floyd跑了一遍，不出所料TLE了
n,m=map(int,input().split())
c=list(map(int,input().split()))
INF=float('inf')
ma=[*n for i in range(n)]
for i in range(m):
u,v,w=map(int,input().split())
ma=w
ma=w#“道路”：双向
for k in range(n):
for i in range(n):
for j in range(n):
ma=min(ma,ma+ma+c)
print(ma)
边集数组
n,m=map(int,input().split())
#节点cost，注意：起点和终点得设为0. ------------
c=list(map(int,input().split()))
c=0
c=0
#------------------------------------------
edges=[]
for i in range(m):
u,v,w=map(int,input().split())
edges.append((u,v,w))
#别忘记双向边
edges.append((v,u,w))留意：起点和终点的cost得洗濯为0（后面会具体解释）
而且本题是双向边，得两次edges.append( )
Bellman-ford算法
从起点向外通报最短路信息，得颠末n-1次松弛才能到达终点
前(n-1)轮检视所有的边(u,v,c)，进行松弛操作（判定所有边能否使新路径更小）：
（假如第n轮还有更小的那就是存在负环了）
sta去v的新路径:从sta先去u城，加上从u城到v的代价c ，还得加上城市点的cost
但是是u城的cost照旧v城的cost？
d[ k ]代表从sta到k点的最小耗费，为了方便统计我们得讲所有在路径上的点的话费都算在里面，这也就是为什么前面需要洗濯起点和终点的cost为0
那么新路径应该加上的不是中介点u的cost，而是新的v的，这点和floyd的点耗费处理差异
（floyd是多源最短路，而bellman是单源最短路）
https://i-blog.csdnimg.cn/direct/c163e155936241c88600c9867061d526.jpeg
def bellman(n,edges,sta,c):
INF=float('inf')
d=*(n+1) #注意输入起始从1开始，所以得n+1 ,初始化无边
d=0 #d数组是从sta到各点的最短路径，自己到自己为0
#n-1轮松弛
for i in range(n-1):
for u,v,w in edges:
if d!=INF:
ncost=d+w+c#注意c的索引
if ncost<d:
#从sta有边到u ，而且新路径更短
d=ncost
#第n轮:检测负环
for u,v,w in edges:
if d!=INF and d+w+c<d:
return None
return d
d=bellman(n,edges,1,c) #注意起始从1开始
if d:
print(d) #从点1到点n
else:
print('有负环')
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]