2194出差-节点开销Bellman-ford/图论

题目网址： 蓝桥账户中央
  

   我先用Floyd跑了一遍，不出所料TLE了

1. n,m=map(int,input().split())
3. c=list(map(int,input().split()))
5. INF=float('inf')
6. ma=[[INF]*n for i in range(n)]
8. for i in range(m):
9.     u,v,w=map(int,input().split())
11.     ma[u-1][v-1]=w
12.     ma[v-1][u-1]=w#“道路”：双向
15. for k in range(n):
16.     for i in range(n):
17.         for j in range(n):
18.             ma[i][j]=min(ma[i][j],ma[i][k]+ma[k][j]+c[k])
20. print(ma[0][n-1])

复制代码

边集数组 

1. n,m=map(int,input().split())
3. #节点cost，注意：起点和终点得设为0. ------------
4. c=list(map(int,input().split()))
6. c[0]=0
7. c[n-1]=0
8. #------------------------------------------
10. edges=[]
12. for i in range(m):
13.     u,v,w=map(int,input().split())
14.     edges.append((u,v,w))
15.     #别忘记双向边
16.     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是单源最短路）
  

1. def bellman(n,edges,sta,c):
2.     INF=float('inf')
3.     d=[INF]*(n+1)           #注意输入起始从1开始，所以得n+1 ,初始化无边
4.     d[sta]=0                #d数组是从sta到各点的最短路径，自己到自己为0
7.     #n-1轮松弛
8.     for i in range(n-1):
9.         for u,v,w in edges:
10.             if d[u]!=INF:
11.                 ncost=d[u]+w+c[v-1]#注意c的索引
12.                 if ncost<d[v]:
13.             #从sta有边到u ，而且新路径更短
14.                     d[v]=ncost
17.     #第n轮:检测负环
18.     for u,v,w in edges:
19.         if d[u]!=INF and d[u]+w+c[v-1]<d[v]:
20.             return None
22.     return d
24. d=bellman(n,edges,1,c) #注意起始从1开始
25. if d:
26.     print(d[n]) #从点1到点n
27. else:
28.     print('有负环')

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。