每日被新算法方式轟炸的一天，今天是dijkstra（堆優化版）以及Bellman_ford ，嘗試理解中，屬于是只能照著代碼大概說一下在干嘛。
47. 參加科學大會
https://kamacoder.com/problempage.php?pid=1047
dijkstra（堆優化版），主要區別用gpt總結了一下
- 第一步，選源點到哪個節點近且該節點未被訪問過
- 第二步，該最近節點被標記訪問過
- 第三步，更新非訪問節點到源點的距離（即更新minDist數組）
其中核心部分主要是最小堆來從當前所有候選路徑中找出距離起點最近的節點，更新它所連接的其他節點的最短路徑值。從堆里取出當前距離起點最近的節點，并嘗試用它來更新所有鄰接點的距離，直到終點被訪問或堆為空。也就是中間while函數的意義，其余代碼主要是構建堆以及處理輸入。
import heapqclass Edge:def __init__(self, to, val):self.to = toself.val = valdef dijkstra(n, m, edges, start, end):grid = [[] for _ in range(n + 1)]for p1, p2, val in edges:grid[p1].append(Edge(p2, val))minDist = [float('inf')] * (n + 1)visited = [False] * (n + 1)pq = []heapq.heappush(pq, (0, start))minDist[start] = 0while pq:cur_dist, cur_node = heapq.heappop(pq)if visited[cur_node]:continuevisited[cur_node] = Truefor edge in grid[cur_node]:if not visited[edge.to] and cur_dist + edge.val < minDist[edge.to]:minDist[edge.to] = cur_dist + edge.valheapq.heappush(pq, (minDist[edge.to], edge.to))return -1 if minDist[end] == float('inf') else minDist[end]# 輸入
n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
start = 1 # 起點
end = n # 終點# 運行算法并輸出結果
result = dijkstra(n, m, edges, start, end)
print(result)
94. 城市間貨物運輸 I
https://kamacoder.com/problempage.php?pid=1152
最主要區別在于Bellman_ford能解決負數的權重的問題，而dijkstra不行，
Bellman_ford算法的核心思想是 對所有邊進行松弛n-1次操作（n為節點數量），從而求得目標最短路。
然后是該算法的核心思想：松弛操作
-
外層循環最多執行
n-1次（這是 Bellman-Ford 的核心步驟） -
每次遍歷所有邊，嘗試更新目標點的最短距離（即“松弛”操作）
-
如果一輪下來沒有任何更新，說明最短路徑已穩定，提前退出循環（優化）
def main():n, m = map(int, input().strip().split())edges = []for _ in range(m):src, dest, weight = map(int, input().strip().split())edges.append([src, dest, weight])minDist = [float("inf")] * (n + 1)minDist[1] = 0 # 起點處距離為0for i in range(1, n):updated = Falsefor src, dest, weight in edges:if minDist[src] != float("inf") and minDist[src] + weight < minDist[dest]:minDist[dest] = minDist[src] + weightupdated = Trueif not updated: # 若邊不再更新，即停止回圈breakif minDist[-1] == float("inf"): # 返還終點權重return "unconnected"return minDist[-1]if __name__ == "__main__":print(main())
)
)
)
)
