|
快两个月了才想起之前做的华为机试的第三题还没有解决掉，通过这几天对路径规划问题的学习，已经掌握了一点这种类型的套路了。该题大概意思如下： 给定一个起点src，要求骑车到达某个终点的最短时间，单位路程等于耗电量。输入输出如下：
'''
第一行输入的数据表示：城市的个数、充满电的电容量C、耗电量/路程（=时间）的系数、充满电所需时间/待充满电量的系数、起点、终点
第二行数据表示：道路的条数，之后的每3个数一组，表示道路直接连通的第一个城市ID、第二个城市ID、之间的距离
第三行表示：加油站的个数、加油站的ID
（城市ID从0开始编号，每一次到达某个城市时，电量必须不小于0，每次充电都是必须充满）
4 7 2 2 0 3
4 0 1 2 0 2 3 1 3 2 2 3 2
1 1 2
输出：
从起点到达终点所需的最短时间，如果不能到达则输出-1
12（0->1->3, 2 + 2 * K1 * K2 + 2 = 12）
'''
这题我目前想到的方法就是采用优先队列，维护一个小顶堆，代码如下：
from queue import PriorityQueue
def grid(flights):
dic = {}
for src, dist, s in flights:
if src not in dic:
dic[src] = {dist: s}
else:
dic[src][dist] = s
return dic
def sesarch(dic, K1, K2, F, C, start, end):
pq = PriorityQueue()
pq.put((0, start, C, F[start])) # (时间，当前节点，当前电量，falg标记该站是否有充电桩)
while not pq.empty():
t, cur, c, flag = pq.get()
if cur == end: return t # 如果到达终点，返回时间t
for next in dic.get(cur, []):
if c >= dic[cur][next] * K1: #如果当前电量能够撑到下一站，则不加油，继续前进
pq.put((t + dic[cur][next], next, c - dic[cur][next] * K1, F[next]))
if flag and C - dic[cur][next] * K1 >= 0: # 如果当前站可以加油，则加（考虑多站之前没有加油桩，得回退到之前经过的存在加油桩的站进行加油的情况），并且需要满足油箱满箱时能够到达下一站
pq.put((t + dic[cur][next] + K2 * (C - c), next, C - dic[cur][next] * K1, F[next]))
return -1
n, C, K1, K2, start, end = map(int, input().split())
line2 = list(map(int, input().split()))
line3 = list(map(int, input().split()))
flights = []
i = 1
while i |