藍橋賬戶中心

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:breaks.append(temp)#用鏈表存儲前驅-->路徑pre = [[i for j in range(n)] for i in range(n)]
print(pre)def floyd(ma):#直接獲得任意兩點之間的最小costd=[[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 ddef buildpath(i, j):path = [j]while i != j:j = pre[i][j]path.append(j)path.reverse()#因為是從終點往前：得掉個頭return pathd=floyd(ma)for i,j in s:print(f'From {i} to {j} :')i-=1j-=1path=buildpath(i,j)print('Path:','-->'.join(str(x+1) for x in path))print('Total cost :',int(d[i][j]))print()

Floyd應用場景：

圖規模較小，須考慮中轉點

能判斷負環（“兜圈子”）