這是基于代碼隨想錄的每日打卡
參加科學大會（第六期模擬筆試）
題目描述
? 小明是一位科學家，他需要參加一場重要的國際科學大會，以展示自己的最新研究成果。
? 小明的起點是第一個車站，終點是最后一個車站。然而，途中的各個車站之間的道路狀況、交通擁堵程度以及可能的自然因素（如天氣變化）等不同，這些因素都會影響每條路徑的通行時間。
? 小明希望能選擇一條花費時間最少的路線，以確保他能夠盡快到達目的地。
輸入描述
? 第一行包含兩個正整數，第一個正整數 N 表示一共有 N 個公共汽車站，第二個正整數 M 表示有 M 條公路。
? 接下來為 M 行，每行包括三個整數，S、E 和 V，代表了從 S 車站可以單向直達 E 車站，并且需要花費 V 單位的時間。
輸出描述
? 輸出一個整數，代表小明從起點到終點所花費的最小時間。
輸入示例
7 9
1 2 1
1 3 4
2 3 2
2 4 5
3 4 2
4 5 3
2 6 4
5 7 4
6 7 9
輸出示例
12
提示信息
? 能夠到達的情況：
? 如下圖所示，起始車站為 1 號車站，終點車站為 7 號車站，綠色路線為最短的路線，路線總長度為 12，則輸出 12。
?
? 
? 不能到達的情況：
? 如下圖所示，當從起始車站不能到達終點車站時，則輸出 -1。
?
? 
?
? 數據范圍：
? 1 <= N <= 500;
1 <= M <= 5000;
堆優化版
import heapq
n,m=map(int,input().split())
graph=[[float('inf') for _ in range(n+1)] for _ in range(n+1)]
visited=[False for _ in range(n+1)]
minDist=[float('inf') for _ in range(n+1)]
for _ in range(m):s,e,t=map(int,input().split())graph[s][e]=tminDist[1]=0
hq=[(0,1)]while hq:# 選擇一個離源點最近的節點且未被訪問過min_dist,cur=heapq.heappop(hq)# 該最近節點標記為訪問過visited[cur]=True# 更新非訪問節點到源點的距離for j in range(1,n+1):if visited[j]==False and min_dist+graph[cur][j]<minDist[j]:minDist[j]=min_dist+graph[cur][j]heapq.heappush(hq,(minDist[j],j))
if minDist[-1]==float('inf'):print(-1)
else:print(minDist[-1])
運行結果
城市間貨物運輸 I
題目描述
? 某國為促進城市間經濟交流，決定對貨物運輸提供補貼。共有 n 個編號為 1 到 n 的城市，通過道路網絡連接，網絡中的道路僅允許從某個城市單向通行到另一個城市，不能反向通行。
? 網絡中的道路都有各自的運輸成本和政府補貼，道路的權值計算方式為：運輸成本 - 政府補貼。權值為正表示扣除了政府補貼后運輸貨物仍需支付的費用；權值為負則表示政府的補貼超過了支出的運輸成本，實際表現為運輸過程中還能賺取一定的收益。
? 請找出從城市 1 到城市 n 的所有可能路徑中，綜合政府補貼后的最低運輸成本。如果最低運輸成本是一個負數，它表示在遵循最優路徑的情況下，運輸過程中反而能夠實現盈利。
? 城市 1 到城市 n 之間可能會出現沒有路徑的情況，同時保證道路網絡中不存在任何負權回路。
輸入描述
? 第一行包含兩個正整數，第一個正整數 n 表示該國一共有 n 個城市，第二個整數 m 表示這些城市中共有 m 條道路。
? 接下來為 m 行，每行包括三個整數，s、t 和 v，表示 s 號城市運輸貨物到達 t 號城市，道路權值為 v （單向圖）。
輸出描述
如果能夠從城市 1 到連通到城市 n， 請輸出一個整數，表示運輸成本。如果該整數是負數，則表示實現了盈利。如果從城市 1 沒有路徑可達城市 n，請輸出 “unconnected”。
輸入示例
6 7
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5
輸出示例
1
提示信息
? 
? 示例中最佳路徑是從 1 -> 2 -> 5 -> 6，路上的權值分別為 1 2 -2，最終的最低運輸成本為 1 + 2 + (-2) = 1。
? 示例 2：
? 4 2
1 2 -1
3 4 -1
? 在此示例中，無法找到一條路徑從 1 通往 4，所以此時應該輸出 “unconnected”。
? 數據范圍：
? 1 <= n <= 1000；
1 <= m <= 10000;
? -100 <= v <= 100;
Bellman_ford算法
n,m=map(int,input().split())
minDist=[float('inf') for _ in range(n+1)] # 表示節點n到原點的最小距離
minDist[1]=0
sides=[list(map(int,input().split())) for _ in range(m)]for _ in range(n-1): # 松弛n-1次updated=Falsefor start,end,value in sides:if minDist[start]+value<minDist[end]:minDist[end]=minDist[start]+valueupdated=Trueif updated==False:breakif minDist[-1]!=float('inf'):print(minDist[-1])
else:print('unconnected')
運行結果
