1656打印路径-Floyd回溯/图论-链表/数据结构

蓝桥账户中心

1.税收：

“城市的税收”：所以是中介点的税收，经过该点后加上

2.路径：

用数组存储前驱节点从而串成链表 

pre[ i ][ j ]代表的是从 i 到 j 的最短路径上 j 的前驱节点是什么

那么便可以pre[ i ][ j ]=k 把k加入path后--> pre[ i ][ k ]=k2等等如此回溯

IO技巧：

因为他输入是-1代表无法到达而不是inf

所以可以先replace('-1','inf')

然后再map(float, )

最后输出的时候记得int( )

n=int(input())


INF=float('inf')
ma=[]


for i in range(n):
    temp=input()
    temp=temp.replace('-1','inf')
    #print(temp)
    ma.append(list(map(float,temp.split()))) ##float

#print(ma)

shui=list(map(int,input().split()))

s=[]
while 1:
    temp=list(map(int,input().split()))
    if temp[0]==temp[1]==-1:
        break
    s.append(temp)

#用链表存储前驱-->路径
    
pre = [[i for j in range(n)] for i in range(n)]
print(pre)



def floyd(ma):#直接获得任意两点之间的最小cost
    
    d=[[ma[i][j] for j in range(n)]for i  in range(n)]

    for k in range(n):#中间节点：shui[k]
        for i in range(n):
            for j in range(n):
                #if d[i][k]!=-1 and d[k][j]!=-1:
                if d[i][j] > d[i][k] + d[k][j] + shui[k]:#更新判断
                    d[i][j] = d[i][k] + d[k][j] + shui[k]#shui:直接加在点上
                    pre[i][j] = pre[k][j]

    return d

def buildpath(i, j):
    path = [j]
    while i != j:
        j = pre[i][j]
        path.append(j)
    path.reverse()#因为是从终点往前：得掉个头
    return path


d=floyd(ma)

for i,j in s:
    print(f'From {i} to {j} :')
    i-=1
    j-=1
    path=buildpath(i,j)
    print('Path:','-->'.join(str(x+1) for x in path))
    print('Total cost :',int(d[i][j]))

    print()

Floyd应用场景：

图规模较小，须考虑中转点

能判断负环（“兜圈子”）