P5839-图论-Floyd算法
在搜刮中bfs只得当无权图若是碰到有权图最简单的方法就是用毗邻矩阵-二维矩阵存储每个点对之间的权重,然后用floyd
1.毗邻矩阵
如果是二维输入权值的话直接append就好了
ma=[]
for i in range(m):
ma.append(list(map(int,input().split()))) 点对输入环境的：
用INF初始化界说没有边无法到达
然后对每个点到自己界说为0，也就是没距离
同时用min读入来处理重边（i到j不止一条路，那么优先选短的）
INF=float('inf')
ma=[*n for _ in range(n)]
for i in range(n):
ma=0
for i in range(m):
a,b,c=map(int,input().split())
ma=min(ma,c)
ma=min(ma,c) 2.floyd算法
本质实在是动态规划
ma数组存储的是每个点之间的直接距离，并没有思量从中节点经过的环境
那么我们只需要再罗列在 i、j 点之间的所有大概点k，用min存储更小的途径
def floyd(ma):
for k in range(m):
for i in range(m):
for j in range(m):
ma=min(ma,ma+ma)
return ma 如果原来的ma数组还会用到，那么最好复制一下ma
d=[ for j in range(m)] for i in range(m)] 注意：不能用dist=ma.copy()
因为二维数组的浅拷贝会导致对拷贝体做更改的时候会影响本体
a=
a2=a.copy()
a2.append(4)
print(a,a2)
print()
b=[,]
b2=b.copy()
b2.append(4)
print(b,b2)
'''输出
[,] [,]
''' P5839
P5839 Moortal Cowmbat G - 洛谷
起首我们跑一边floyd得出最小代价
INF = float('inf')
n, m, k = map(int, input().split())
s = input()
ma =
def floyd(ma):
d = [ for j in range(m)] for i in range(m)]
for k in range(m):
for i in range(m):
for j in range(m):
d = min(d, d + d)
return d
d = floyd(ma) 背面就是得规划我们该如何变我们的字符串
dp状态: F[ i ]表现到i位置全部合法的最小代价
dp转移: F[ i ]=F[ j ]+k( i,j ) 其中k( i,j )表现 i 到 j 全部改为一种颜色的最小代价，这里可以用前缀和举行预处理
#前缀和
su = [*(n+1) for i in range(m)]
for i in range(m):
for j in range(1, n+1):# 从1开始到n
su = su + d)-ord('a')]
f = *(n+1)
f = 0
mx = *m
for i in range(k, n+1):
for col in range(m):
mx = max(mx, su-f)
for col in range(m):
f = min(f, su-mx)
print(f)
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]