2026-09-27最多 K 个连续相同字符的最短路径。用go语言有一个包含 n 个节点的有向图节点编号为 0 到 n-1。图中的边由 edges 给出每个元素 [u, v, w] 表示一条从 u 指向 v 的边并且这条边的权重是 w。每个节点 i 都有一个对应字符 labels[i]。另外给定一个整数 k。现在需要从节点 0 走到节点 n-1。路径会依次经过若干节点把这些节点的字符按经过顺序连接起来会得到一个字符串。要求这个字符串中任意同一种字符连续出现的次数都不能超过 k。在满足这个标签限制的所有从 0 到 n-1 的路径中求路径上所有边权之和的最小值。如果不存在满足条件的路径则返回 -1。1 n labels.length 50000。0 edges.length 50000。edges[i] [ui, vi, wi]。0 ui, vi n - 1。ui ! vi。1 wi 10000。labels 由小写英文字母组成。1 k 50。输入 n 3, edges [[0,1,1],[1,2,1],[0,2,3]], labels “aab”, k 1。输出 3。解释从节点 0 到节点 2 的最优有效路径如下使用 edges[2] [0, 2, 3] 到达节点 2边权 wi 3。对应的标签拼接结果为 “ab”满足最多有 k 1 个连续相同字符。因此答案为 3。题目来自力扣3970。大体步骤如下理解路径标签限制路径从节点 0 出发依次经过若干节点最终到达节点 n-1。每经过一个节点就把该节点的 labels 字符拼接到路径字符串末尾。要求这个字符串中任意一种字符连续出现的次数不能超过 k。注意连续相同字符只和相邻节点标签有关。如果当前节点标签和下一个节点标签相同那么连续计数加一如果不同连续计数重新变成 1。起点节点的标签也要算进去所以起点本身的连续计数初始为 1。建图根据 edges 建立有向图的邻接表。对于每条边 [u, v, w]表示从 u 到 v 有一条权重为 w 的有向边。后续从某个节点扩展时就遍历它的所有出边。定义状态状态需要包含两部分信息第一当前所在节点 x。第二到达 x 时路径末尾连续相同标签的数量 cnt。对于每个状态需要记录从起点 0 到当前节点 x并且末尾连续计数为 cnt 时的最小总边权。因此使用一个二维距离表dis[x][cnt] 表示到达节点 x且末尾连续相同字符数为 cnt 时的最小边权和。其中 cnt 的取值范围是 1 到 k因为一旦超过 k 就不合法不需要继续考虑。初始化所有 dis[x][cnt] 初始化为无穷大表示暂时不可达。起点是节点 0。起点本身有一个标签所以它自己的末尾连续相同字符数为 1。因此 dis[0][1] 0。然后把状态 (当前总边权 0, 当前节点 0, 当前连续计数 1) 放入优先队列。优先队列按照当前总边权从小到大排序这就是 Dijkstra 算法的基础。使用优先队列进行最短路扩展只要优先队列不为空就重复以下过程第一从优先队列中弹出当前总边权最小的状态。这个状态包含当前距离 d、当前节点 x、当前连续计数 cnt。第二如果当前节点 x 已经是终点 n-1那么直接返回 d。因为优先队列每次弹出的是当前已知最小距离所以第一次弹出终点状态时得到的就是满足标签限制的最小总边权。第三如果当前距离 d 大于已经记录的 dis[x][cnt]说明这是一个过期的旧状态直接跳过。第四遍历当前节点 x 的所有出边。对于每条出边假设它通向节点 y边权为 w。计算到达 y 后的新连续计数 newCnt如果 labels[y] 和 labels[x] 相同说明连续相同字符延续newCnt cnt 1。如果 labels[y] 和 labels[x] 不同说明连续相同字符中断newCnt 1。然后计算新的总边权 newDis d w。第五判断这个新状态是否合法且更优如果 newCnt 小于等于 k说明没有超过连续相同字符限制。并且 newDis 小于 dis[y][newCnt]说明找到了到达 y 且末尾连续计数为 newCnt 的更短路径。那么就更新 dis[y][newCnt] newDis并把新状态放入优先队列。无法到达终点时如果优先队列一直处理到空都没有在弹出时遇到终点 n-1说明不存在满足标签限制的路径。此时返回 -1。结合示例理解题目示例中n 3edges [[0,1,1], [1,2,1], [0,2,3]]labels “aab”k 1。起点是 0标签是 a初始连续计数为 1。路径 0 - 1 - 2节点标签依次是 a、a、b。前两个 a 连续出现两次连续计数达到 2超过 k 1所以这条路径不合法。路径 0 - 2节点标签依次是 a、b。连续相同字符最多为 1满足 k 1。边权为 3所以答案是 3。代码会在优先队列中先考虑较小总边权的路径但不合法的状态会在 newCnt k 时被过滤掉最终返回合法路径的最小总边权 3。为什么需要二维距离表如果只记录到达某个节点的最小距离而不记录末尾连续相同字符数可能会丢失信息。例如到达同一个节点时距离较大但末尾连续计数较小的路径后续可能还能继续走而距离较小但末尾连续计数较大的路径后续可能因为超过 k 而不能走。所以必须把“节点 末尾连续计数”作为一个完整状态来做最短路。正确性要点图中所有边权都是正数因此可以使用 Dijkstra 算法。优先队列保证每次扩展的都是当前总边权最小的状态。状态中包含了连续相同字符数因此所有标签限制都能在扩展时判断。只要某个状态合法且被更新就会进入优先队列。第一次弹出终点状态时得到的就是所有合法路径中的最小总边权。时间复杂度状态数量最多为 n 乘以 k也就是 O(nk)。每条边可能从不同连续计数状态被遍历因此边扩展次数最多为 O(kE)。每次优先队列插入或弹出需要 O(log(kE)) 或 O(log(nkE)) 的时间。所以总时间复杂度可以表示为 O((nk kE) log(kE))通常简写为 O(kE log(kE))因为 k 最大 50E 最多 50000。更保守地写O(kE log(kE))。额外空间复杂度邻接表需要 O(n E)。距离表 dis 需要 O(nk)。优先队列最坏情况下可能积累 O(kE) 个状态。因此额外空间复杂度保守为 O(nk E kE)通常可以简写为 O(nk E) 或 O(kE nk E)。如果只按核心状态表计算空间是 O(nk E)如果严格考虑优先队列中的重复状态最坏是 O(kE nk E)。Go完整代码如下packagemainimport(container/heapfmtmath)funcshortestPath(nint,edges[][]int,labelsstring,kint)int{typeedgestruct{to,wint}g:make([][]edge,n)for_,e:rangeedges{x,y,w:e[0],e[1],e[2]g[x]append(g[x],edge{y,w})}dis:make([][]int,n)fori:rangedis{dis[i]make([]int,k1)forj:rangedis[i]{dis[i][j]math.MaxInt}}h:hp{{0,0,1}}forlen(h)0{top:heap.Pop(h).(tuple)d:top.dis x,cnt:top.x,top.cntifxn-1{returnd}ifddis[x][cnt]{continue}for_,e:rangeg[x]{y:e.to newCnt:1iflabels[y]labels[x]{newCntcnt1}newDis:de.wifnewCntknewDisdis[y][newCnt]{dis[y][newCnt]newDis heap.Push(h,tuple{newDis,y,newCnt})}}}return-1}// 最短路长度, 节点编号, 最后连续相同字母个数typetuplestruct{dis,x,cntint}typehp[]tuplefunc(h hp)Len()int{returnlen(h)}func(h hp)Less(i,jint)bool{returnh[i].dish[j].dis}func(h hp)Swap(i,jint){h[i],h[j]h[j],h[i]}func(h*hp)Push(v any){*happend(*h,v.(tuple))}func(h*hp)Pop()(v any){a:*h;*h,va[:len(a)-1],a[len(a)-1];return}funcmain(){n:3edges:[][]int{{0,1,1},{1,2,1},{0,2,3}}labels:aabk:1result:shortestPath(n,edges,labels,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importheapqimportmathdefshortestPath(n,edges,labels,k):# 建图g[[]for_inrange(n)]foru,v,winedges:g[u].append((v,w))INFmath.inf# dist[i][c] 表示到达节点 i 时末尾连续相同标签数量为 c 的最小边权和dist[[INF]*(k1)for_inrange(n)]ifk1:return-1# 起点为节点 0初始连续相同标签数量为 1dist[0][1]0# 优先队列元素(当前总权重, 当前节点, 当前末尾连续相同标签数量)pq[(0,0,1)]whilepq:d,x,cntheapq.heappop(pq)ifddist[x][cnt]:continue# 第一次弹出终点时即为最小总边权ifxn-1:returndfory,wing[x]:iflabels[y]labels[x]:new_cntcnt1else:new_cnt1new_disdwifnew_cntkandnew_disdist[y][new_cnt]:dist[y][new_cnt]new_dis heapq.heappush(pq,(new_dis,y,new_cnt))return-1if__name____main__:n3edges[[0,1,1],[1,2,1],[0,2,3]]labelsaabk1resultshortestPath(n,edges,labels,k)print(result)C完整代码如下#includebits/stdc.husingnamespacestd;structState{intd,x,cnt;booloperator(constStateother)const{returndother.d;// 小顶堆}};intshortestPath(intn,vectorvectorintedges,string labels,intk){if(k1)return-1;// 起点本身就有一个字符k 至少为 1 才可能有效vectorvectorpairint,intg(n);for(autoe:edges){intue[0],ve[1],we[2];g[u].push_back({v,w});}constintINFINT_MAX;// dis[i][c] 表示到达节点 i 时末尾连续相同标签数量为 c 的最小边权和vectorvectorintdis(n,vectorint(k1,INF));priority_queueState,vectorState,greaterStatepq;dis[0][1]0;pq.push({0,0,1});while(!pq.empty()){State toppq.top();pq.pop();intdtop.d,xtop.x,cnttop.cnt;if(xn-1)returnd;if(ddis[x][cnt])continue;for(auto[y,w]:g[x]){intnewCnt1;if(labels[y]labels[x]){newCntcnt1;}intnewDisdw;if(newCntknewDisdis[y][newCnt]){dis[y][newCnt]newDis;pq.push({newDis,y,newCnt});}}}return-1;}intmain(){intn3;vectorvectorintedges{{0,1,1},{1,2,1},{0,2,3}};string labelsaab;intk1;intresultshortestPath(n,edges,labels,k);coutresultendl;return0;}