解决leetcode第3977题有限电量到达目标节点的最少时间

3977.有限电量到达目标节点的最少时间难度困难问题描述给你一个有n个节点的有向加权图节点编号从0到n-1。该图由一个二维整数数组edges表示其中edges[i][ui,vi,ti]表示一条从节点ui到节点vi的有向边通过该边需要花费ti秒。同时给你一个整数power表示初始可用电量以及一个长度为n的整数数组cost其中cost[u]表示从节点u通过任意一条出边转发信号所需的电量。给你两个整数source和target。信号在时间0从source出发拥有power单位的电量并遵循以下规则只有当剩余电量至少为cost[u]时信号才能遍历从节点u出发的有向边。信号到达一个节点时不消耗任何电量除非它稍后通过另一条边离开该节点。当信号从节点u转发时剩余电量将减少cost[u]个单位。遍历一条边edges[i][ui,vi,ti]会使总时间增加ti秒。返回一个大小为2的整数数组answer其中answer[0]是信号到达节点target所需的最小时间。answer[1]是所有实现answer[0]的路径中最大的剩余电量。如果信号无法到达target则返回[-1,-1]。示例1输入n5,edges[[0,1,1],[1,4,1],[0,2,1],[2,3,1],[3,4,1]],power4,cost[2,3,1,1,1],source0,target4输出[3,0]解释信号从节点0出发拥有4个单位的电量。路径0-1-4无效因为离开节点0后信号剩余2个单位的电量这小于cost[1]3。有效路径0-2-3-4总共花费时间为3。沿着这条路径消耗的总电量为cost[0]cost[2]cost[3]4剩余电量为0。因此答案为[3,0]。示例2输入n3,edges[[0,1,2],[1,2,2],[2,0,2]],power3,cost[1,1,1],source1,target1输出[0,3]解释由于source和target是同一个节点不需要通过任何节点。因此花费的最小总时间为0并且不消耗电量。因此答案为[0,3]。示例3输入n4,edges[[0,1,3],[2,3,4]],power3,cost[1,1,1,1],source0,target3输出[-1,-1]解释没有从source到target的有效路径因此返回[-1,-1]。提示1n10000edges.length1000edges[i][ui,vi,ti]0ui,vin-11ti10**91power1000cost.lengthn1cost[i]20000source,targetn-1​问题分析本题在输入原始数据时节点数n可以不输入因为cost的数据长度决定了节点的个数同时edges中也可以看出最大节点这些都可以确定节点个数n的值所以在本题中没有输入n的环节。要从source节点通过有向边到达target节点首先是在edges中找到所有起始节点为source的有向边然后从这些有向边开始遍历其它有向边如果最终能够到达target节点将这些从source到target的有向边存储起来最后在主程序中根据这些有向边的数据信息和cost中消耗的电量信息将各条路径到达target节点消耗电量之后剩余的电量以及所需要的时间以列表的方式给出再找出其中时间最短但剩余的电量最大输出即可如果surce和target相同则直接给出结果[0,power]程序如下#根据给定的source_edge如果能够在edges中能够形成一条完整的路径返回路径否则返回空路径 def get_one_paths(edges,source_edge,target): paths [] ssource_edge[0] tsource_edge[1] paths.append(source_edge) if ttarget: return paths nlen(edges) for i in range(1,n): st for j in edges: if j[0]s: tj[1] if ttarget: paths.append(j) return paths else: paths.append(j) else: return [] #根据有向节点找出所有从source到target的所有路径并返回 def get_all_paths(edges,source,target): paths [] sourceslist(x for x in edges if x[0]source ) for i in sources: pathget_one_paths(edges,i,target) if path![]: paths.append(path) return paths #主程序 edgeseval(input(enter the edges )) powerint(input(enter the power )) costeval(input(enter the cost )) sourceeval(input(enter the source )) targeteval(input(enter the target )) if sourcetarget: result[0,power] else: paths get_all_paths(edges, source, target) t [] for i in paths: e list(x[0] for x in i) p power - sum(list(cost[x] for x in e)) s sum(list(x[2] for x in i)) if p 0: t.append([s, p]) if t []: result[-1,-1] else: a min(list(x[0] for x in t)) b max(list(x[1] for x in t if x[0] a)) result[a,b] print(result)运行实例一​​enter the edges [[0,1,1],[1,5,1],[0,2,1],[2,5,1],[2,3,2],[3,4,1],[4,5,1]]enter the power 4enter the cost [1,2,1,1,1]enter the source 0enter the target 5[2, 2]​​运行实例二enter the edges [[0,1,2],[1,2,2],[2,0,2]]enter the power 3enter the cost [2,2,2]enter the source 1enter the target 1[0, 3]运行实例三enter the edges [[0,1,2],[3,4,2]]enter the power 3enter the cost [2,2,2,2]enter the source 0enter the target 3[-1, -1]​​