逆序思维,从所有点被删除开始,每次添加一个点,并更新所有途径该点的路径,只取符合条件的答案,此时答案一定是符合条件的,因为其值一定是只使用后面数个点更新的
python
n = int(input())
dis = [list(map(int, input().split())) for _ in range(n)]
st = [0]*n
x = list(map(int, input().split()))
INF = int(1e9)
flag = [[0]*n for _ in range(n)]
res = 0
resl = []
# 每次从后往前更新最短路
for xi in range(n-1, -1, -1):
k = x[xi]-1
st[k] = 1
# 每次用该点将所有以该点作为途径点的路径更新
for i in range(n):
for j in range(n):
# 若此点被取过,需要减去之前所取值
if st[i] and st[j] and flag[i][j] == 1:
res -= dis[i][j]
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
# 仅取符合条件的答案
# 注意,该答案一定是只剩后xi个点最优的
if st[i] and st[j]:
res += dis[i][j]
flag[i][j] = 1
resl.append(res)
# 倒序打印答案
for i in range(n-1, -1, -1):
print(resl[i], end=" ")
算法1
Floyd