陕西省网站备案商城网站建设哪家效益快

陕西省网站备案,商城网站建设哪家效益快,平面设计培训班哪里有,专业团队建设实施方案2025-12-15#xff1a;有向图中到达终点的最少时间。用go语言#xff0c;给出一个有向图和一个整数 n#xff0c;图中节点编号为 0 到 n-1。每条边用四元组 edges[i] [ui, vi, starti, endi] 描述#xff0c;表示从 ui 指向 vi 的这条边只有在某些时刻可用#xff1a;只有…2025-12-15有向图中到达终点的最少时间。用go语言给出一个有向图和一个整数 n图中节点编号为 0 到 n-1。每条边用四元组 edges[i] [ui, vi, starti, endi] 描述表示从 ui 指向 vi 的这条边只有在某些时刻可用只有当当前的整数时刻 t 落在区间 [starti, endi]含端点时才能沿该边移动。你在时刻 0 位于节点 0。每经过一个单位时间可以选择两种行为之一留在当前节点不动如果存在一条从当前节点出发的边并且此时刻 t 在该边允许的时间区间内则沿该有向边移动到相应的邻接节点。求到达节点 n-1 所需的最小时间以整数时刻计。如果无法到达返回 -1。1 n 100000。0 edges.length 100000。edges[i] [ui, vi, starti, endi]。0 ui, vi n - 1。ui ! vi。0 starti endi 1000000000。输入: n 4, edges [[0,1,0,3],[1,3,7,8],[0,2,1,5],[2,3,4,7]]。输出: 5。解释:最佳路径为在节点 0 等待直到时间 t 1然后走边 (0 → 2)该边在 1 到 5 的时间段内可用。你在 t 2 到达节点 2。在节点 2 等待直到时间 t 4然后走边 (2 → 3)该边在 4 到 7 的时间段内可用。你在 t 5 到达节点 3。因此到达节点 3 的最小时间是 5。题目来自力扣3604。分步骤过程描述图构建阶段代码首先将输入的四元组边edges[i] [ui, vi, starti, endi]转换为邻接表表示的图。每个节点对应一个列表存储从其出发的边信息。每条边记录目标节点to、边可用的起始时间start和结束时间end。例如对于输入示例节点0有两条边一条指向节点1时间窗口[0,3]另一条指向节点2时间窗口[1,5]。数据初始化初始化一个距离数组dis长度为节点数n所有元素初始化为极大值math.MaxInt表示初始时从节点0到各节点的最短时间未知。例外是dis[0] 0因为起点时刻为0。创建一个最小堆优先队列h用于按时间顺序处理节点。堆中存储pair结构包含当前时间d和节点编号x。初始时将起点(d0, x0)加入堆。主循环Dijkstra核心逻辑循环从堆中弹出时间最小的pair即当前最早可处理的节点。若弹出的时间d大于dis[x]说明该节点已被更优路径更新则直接跳过避免重复计算。若当前节点x是终点n-1立即返回d作为答案因此时已找到最短时间。遍历节点x的所有出边。对于每条边计算新时间移动需满足边的时间窗口约束。首先必须等待至边可用若当前时间d小于边的起始时间start则等待到start然后移动耗时1单位。因此新时间newD max(d, e.start) 1。验证时间窗口移动操作开始的时刻即newD - 1必须在边的结束时间end之前即newD - 1 e.end。否则边已失效不可用。更新距离若上述条件满足且newD小于目标节点y的当前最短时间dis[y]则更新dis[y] newD并将(newD, y)加入堆供后续处理。等待行为的隐式处理算法通过max(d, e.start)自动处理节点等待若当前时间早于边起始时间则等待至start否则立即移动。这模拟了题目中“留在当前节点不动”的选项无需显式操作。终止条件若堆为空仍未到达终点返回-1表示终点不可达。例如若所有边的时间窗口过早结束或路径不连通则会触发此情况。时间复杂度与空间复杂度时间复杂度算法基于Dijkstra的优先队列实现。每个节点最多被处理一次通过dis数组去重但每条边可能触发一次堆操作插入或更新。堆操作插入或弹出复杂度为O(log N)其中N为节点数。因此总复杂度为O((N E) log N)其中E为边数。空间复杂度主要空间消耗为邻接表存储图O(E)。距离数组disO(N)。优先队列堆最坏情况下存储O(N)个节点。总空间复杂度为O(N E)。此方案通过扩展Dijkstra算法高效结合了时间窗口约束适用于大规模图N和E可达100,000。Go完整代码如下packagemainimport(container/heapfmtmath)funcminTime(nint,edges[][]int)int{typeedgestruct{to,start,endint}g:make([][]edge,n)for_,e:rangeedges{x,y:e[0],e[1]g[x]append(g[x],edge{y,e[2],e[3]})}dis:make([]int,n)fori:rangedis{dis[i]math.MaxInt}dis[0]0h:hp{{}}forlen(h)0{p:heap.Pop(h).(pair)d:p.d x:p.xifddis[x]{continue}ifxn-1{returnd}for_,e:rangeg[x]{y:e.to newD:max(d,e.start)1ifnewD-1e.endnewDdis[y]{dis[y]newD heap.Push(h,pair{newD,y})}}}return-1}typepairstruct{d,xint}typehp[]pairfunc(h hp)Len()int{returnlen(h)}func(h hp)Less(i,jint)bool{returnh[i].dh[j].d}func(h hp)Swap(i,jint){h[i],h[j]h[j],h[i]}func(h*hp)Push(v any){*happend(*h,v.(pair))}func(h*hp)Pop()(v any){a:*h;*h,va[:len(a)-1],a[len(a)-1];return}funcmain(){n:4edges:[][]int{{0,1,0,3},{1,3,7,8},{0,2,1,5},{2,3,4,7}}result:minTime(n,edges)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importheapqimportmathfromtypingimportListdefminTime(n:int,edges:List[List[int]])-int:# 构建图每个元素是 (邻接节点, start, end)graph[[]for_inrange(n)]foreinedges:x,y,start,ende graph[x].append((y,start,end))# 初始化距离数组dist[math.inf]*n dist[0]0# 优先队列存储 (距离, 节点)pq[(0,0)]# (当前时间, 节点)whilepq:d,xheapq.heappop(pq)# 如果当前距离不是最短距离跳过ifddist[x]:continue# 到达终点ifxn-1:returnint(d)# 遍历邻接边fory,start,endingraph[x]:# 计算新到达时间必须至少等到 start 时刻new_dmax(d,start)1# 检查是否在有效时间内且距离更短ifnew_d-1endandnew_ddist[y]:dist[y]new_d heapq.heappush(pq,(new_d,y))return-1# 测试用例if__name____main__:n4edges[[0,1,0,3],[1,3,7,8],[0,2,1,5],[2,3,4,7]]resultminTime(n,edges)print(result)# 输出结果C完整代码如下#includeiostream#includevector#includequeue#includeclimits#includealgorithmusingnamespacestd;structEdge{intto,start,end;Edge(intt,ints,inte):to(t),start(s),end(e){}};structNode{inttime,id;Node(intt,inti):time(t),id(i){}// 重载运算符用于最小堆booloperator(constNodeother)const{returntimeother.time;}};intminTime(intn,vectorvectorintedges){// 构建图vectorvectorEdgegraph(n);for(constautoe:edges){intxe[0],ye[1],starte[2],ende[3];graph[x].emplace_back(y,start,end);}// 初始化距离数组vectorintdist(n,INT_MAX);dist[0]0;// 优先队列最小堆priority_queueNode,vectorNode,greaterNodepq;pq.emplace(0,0);while(!pq.empty()){Node currpq.top();pq.pop();intdcurr.time;intxcurr.id;// 如果当前距离不是最短距离跳过if(ddist[x]){continue;}// 到达终点if(xn-1){returnd;}// 遍历邻接边for(constautoe:graph[x]){intye.to;intstarte.start;intende.end;// 计算新到达时间必须至少等到 start 时刻intnew_dmax(d,start)1;// 检查是否在有效时间内且距离更短if(new_d-1endnew_ddist[y]){dist[y]new_d;pq.emplace(new_d,y);}}}return-1;}intmain(){intn4;vectorvectorintedges{{0,1,0,3},{1,3,7,8},{0,2,1,5},{2,3,4,7}};intresultminTime(n,edges);coutresultendl;return0;}