算法競賽進階指南：裝滿的油箱（Python）

題目描述：

有 N 個城市（編號0、1…N−1）和 MM 條道路，構成一張無向圖。

在每個城市裡邊都有一個加油站，不同的加油站的單位油價不一樣。

現在你需要回答不超過 100 個問題，在每個問題中，請計算出一架油箱容量為 C 的車子，從起點城市 S 開到終點城市 E 至少要花多少油錢？

注意： 假定車子初始時油箱是空的。

輸入格式

第一行包含兩個整數 N 和 M。

第二行包含 N 個整數，代表 N 個城市的單位油價，第 i 個數即為第 i 個城市的油價 pi。

接下來 M 行，每行包括三個整數 u,v,d，表示城市 u 與城市 v 之間存在道路，且車子從 u 到 v 需要消耗的油量為 d。

接下來一行包含一個整數 q，代表問題數量。

接下來 q 行，每行包含三個整數 C、S、E，分別表示車子油箱容量 C、起點城市 S、終點城市 E。

輸出格式

對於每個問題，輸出一個整數，表示所需的最少油錢。

如果無法從起點城市開到終點城市，則輸出 impossible。

每個結果占一行。

數據范圍

1≤N≤1000,
1≤M≤10000,
1≤pi≤100,
1≤d≤100,
1≤C≤100

輸入樣例：

5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4

輸出樣例：

170
impossible

解析： 

本題解法較為單一 dijkstra + 拆點法

在寫這篇文章前 看到CSDN上已經有幾篇講解詳細的題解了 不過都是C++實現的

這裡貼一份Python3實現的完整代碼 並附有詳細注釋 有需要可以參考一下

代碼：

import heapq # 堆優化的dijkstra
N,M = map(int,input().split())
INF = float('inf')
price = list(map(int,input().split()))
Map = [dict() for i in range(N)] # 字典存圖 比鄰接矩陣存圖省空間
for i in range(M) :
a,b,c = map(int,input().split())
Map[a][b] = Map[b][a] = c # 無向圖 => 雙向邊
def dijkstra(cap,start,end) :
# st[i][j]:是否更新過在點i有j升油時的狀態
st = [[0 for i in range(cap+1)]for j in range(N)]
# dis[i][j]:在點i有j升油時的最小花費
dis = [[INF for i in range(cap+1)]for j in range(N)]
dis[start][0] = 0 # 開始沒有花費
queue = [(0,start,0)]
heapq.heapify(queue)
while len(queue) :
d,node,c = heapq.heappop(queue)
if node == end : return d # 如果當前點是終點 直接返回結果 即最小花費
if st[node][c] : continue # 如果這個狀態被訪問過了
st[node][c] = 1 # 否則標記為已訪問
if c < cap : # 加一升油更新狀態的情況
if dis[node][c+1] > d + price[node] and not st[node][c+1]:
dis[node][c+1] = d + price[node]
heapq.heappush(queue,(dis[node][c+1],node,c+1))
for next in Map[node].keys() : # 前往下一個點更新狀態的情況
if c >= Map[node][next] :
if dis[next][c-Map[node][next]] > d and not st[next][c-Map[node][next]] :
dis[next][c-Map[node][next]] = d
heapq.heappush(queue,(dis[next][c-Map[node][next]],next,c-Map[node][next]))
return -1 # 不能到達終點 最後將會返回-1
q = int(input())
for _ in range(q) :
C,S,E = map(int,input().split())
ans = dijkstra(C,S,E)
if ans == -1 : print('impossible')
else : print(ans)