AtCoder Beginner Contest 416 vp

AtCoder Beginner Contest 416

Development(有修改floyd)

观察数据范围，对于n=500的图论问题可以使用Floyd算法，n^3应该是跑不满的。

本题中的机场可以看作是一个超级源点，即令0与所有设立了机场的城市相连，来回权重设为T/2。为了防止浮点数的出现，将所有的权重乘二。

问题中会对图进行修改，注意到floyd算法的本质是枚举中间节点，对于修改，枚举新的路径的城市作为中间节点，重新做Floyd算法递推，可以在n^2的时间复杂度内更新距离。

# 加快
min=lambda x,y:x if x<y else y
inf=10**18

n,m=RR()
# 建图
g=[[inf]*(n+1) for _ in range(n+1)]
for i in range(m):
    u,v,w=RR()
    g[u][v]=g[v][u]=min(g[u][v],2*w)
    
# 建立源点
k,t=RR()
for u in RR():
    g[0][u]=g[u][0]=t

# floyd递推
f=g
for i in range(n+1):
    f[i][i]=0

for k in range(n+1):
    for i in range(n+1):
        for j in range(n+1):
            f[i][j]=min(f[i][j],f[i][k]+f[k][j])
# 更新逻辑，将新的路径的端点作为中间节点，再次递推
def update(u,v):
    # global ans
    for k in {u,v}:
        for i in range(n+1):
            for j in range(n+1):
                f[i][j]=min(f[i][j],f[i][k]+f[k][j])

for _ in range(R()):
    q=RR()
    if q[0]==1:
        x,y,w=q[1:]
        # 更新
        f[x][y]=f[y][x]=min(f[x][y],2*w)
        update(x,y)
    elif q[0]==2:
        # 更新
        f[0][q[1]]=f[q[1]][0]=min(f[q[1]][0],t)
        update(0,q[1])
    else:
        # 给定的数据范围可以暴力求解
        ans=0
        for i in range(1,n+1):
            tmp=f[i]
            for j in range(1,n+1):
                if tmp[j]!=inf:ans+=tmp[j]
        print(ans//2)# 最后整除二