算法竞赛进阶指南:装满的油箱(Python)

发布时间:2024-03-03 12:01

题目描述:

有 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)

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号