原题传送门
代码
# 输入数据
line = input().strip().split()
c, n, s, m = [int(x) for x in line]
line = input().strip().split()
bikes = [float('inf')]
for i in range(len(line)):bikes.append(int(line[i]) - c / 2)
roads = [{} for _ in range(n + 1)]
for i in range(m):line = input().strip().split()a, b, c = [int(x) for x in line]roads[a][b] = roads[b][a] = c
travseral = [False for _ in range(n + 1)]
distance = [float('inf') for _ in range(n + 1)]
travseral[0] = True
distance[0] = 0
pre_points = [[] for _ in range(n + 1)] # 前驱节点
path = []
temp_path = []
min_need = float('inf')
min_back = float('inf')# —————————————————————进入DFS核心代码—————————————————————
def DFS(v: int):global min_needglobal min_backglobal pathglobal temp_pathtemp_path.append(v)if v == 0:need = 0back = 0# 打白条temp = temp_path[0:len(temp_path) - 1]temp.reverse()for each in temp:if bikes[each] > 0: # 如果该站点的自行车多余back += bikes[each]elif back > -bikes[each]: # 如果带回去的自行车能够填补该站点back += bikes[each]else:need += -back - bikes[each]back = 0if need < min_need:min_need = needmin_back = backpath = temp_path[0:]elif need == min_need and back < min_back:min_back = backpath = temp_pathelse:passtemp_path.pop()else:for each in pre_points[v]:DFS(each)temp_path.pop()# —————————————————————结束DFS核心代码—————————————————————
def main():# ————————————————————进入Dijkstra核心代码————————————————————# dijkstra算法，每次添加一个bike stationfor _ in range(n):min_distance = float('inf')station = -1 # 添加的车站temp_pre = [] # 添加的路径for j in range(n + 1):if travseral[j]: # 该点已经被遍历for h in range(n + 1):if not travseral[h]:temp = intif j == h:temp = 0elif h not in roads[j]:temp = float('inf')elif h in roads[j]:temp = roads[j][h]else:passif distance[j] + temp < min_distance:min_distance = distance[j] + tempstation = htemp_pre = [j]elif distance[j] + temp == min_distance and station == h:temp_pre.append(j)pre_points[station] = temp_predistance[station] = min_distancetravseral[station] = True# ————————————————————结束Dijkstra核心代码————————————————————DFS(s)path.reverse()print(int(min_need), '->'.join(str(x) for x in path), int(min_back))if __name__ == '__main__':main()