算法竞赛进阶指南：装满的油箱（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)