2026-09-27：最多 K 个连续相同字符的最短路径。用go语言，有一个包含 n 个节点的有向图，节点编号为 0 到 n-1。图中的边由 edges 给出，每个元素 [u, v, w] 表示一条从

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 = 3，edges = [[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(nk+E)) 的时间。

所以总时间复杂度可以表示为 O((nk + kE) log(kE))，通常简写为 O(kE log(kE))，因为 k 最大 50，E 最多 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/heap""fmt""math")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,k+1)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.cntifx==n-1{returnd}ifd>dis[x][cnt]{continue}for_,e:=rangeg[x]{y:=e.to newCnt:=1iflabels[y]==labels[x]{newCnt=cnt+1}newDis:=d+e.wifnewCnt<=k&&newDis<dis[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].dis<h[j].dis}func(h hp)Swap(i,jint){h[i],h[j]=h[j],h[i]}func(h*hp)Push(v any){*h=append(*h,v.(tuple))}func(h*hp)Pop()(v any){a:=*h;*h,v=a[:len(a)-1],a[len(a)-1];return}funcmain(){n:=3edges:=[][]int{{0,1,1},{1,2,1},{0,2,3}}labels:="aab"k:=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))INF=math.inf# dist[i][c] 表示到达节点 i 时，末尾连续相同标签数量为 c 的最小边权和dist=[[INF]*(k+1)for_inrange(n)]ifk<1:return-1# 起点为节点 0，初始连续相同标签数量为 1dist[0][1]=0# 优先队列元素：(当前总权重, 当前节点, 当前末尾连续相同标签数量)pq=[(0,0,1)]whilepq:d,x,cnt=heapq.heappop(pq)ifd>dist[x][cnt]:continue# 第一次弹出终点时，即为最小总边权ifx==n-1:returndfory,wing[x]:iflabels[y]==labels[x]:new_cnt=cnt+1else:new_cnt=1new_dis=d+wifnew_cnt<=kandnew_dis<dist[y][new_cnt]:dist[y][new_cnt]=new_dis heapq.heappush(pq,(new_dis,y,new_cnt))return-1if__name__=="__main__":n=3edges=[[0,1,1],[1,2,1],[0,2,3]]labels="aab"k=1result=shortestPath(n,edges,labels,k)print(result)

C++完整代码如下：

#includeusingnamespacestd;structState{intd,x,cnt;booloperator>(constState&other)const{returnd>other.d;// 小顶堆}};intshortestPath(intn,vector<vector<int>>&edges,string labels,intk){if(k<1)return-1;// 起点本身就有一个字符，k 至少为 1 才可能有效vector<vector<pair<int,int>>>g(n);for(auto&e:edges){intu=e[0],v=e[1],w=e[2];g[u].push_back({v,w});}constintINF=INT_MAX;// dis[i][c] 表示到达节点 i 时，末尾连续相同标签数量为 c 的最小边权和vector<vector<int>>dis(n,vector<int>(k+1,INF));priority_queue<State,vector<State>,greater<State>>pq;dis[0][1]=0;pq.push({0,0,1});while(!pq.empty()){State top=pq.top();pq.pop();intd=top.d,x=top.x,cnt=top.cnt;if(x==n-1)returnd;if(d>dis[x][cnt])continue;for(auto&[y,w]:g[x]){intnewCnt=1;if(labels[y]==labels[x]){newCnt=cnt+1;}intnewDis=d+w;if(newCnt<=k&&newDis<dis[y][newCnt]){dis[y][newCnt]=newDis;pq.push({newDis,y,newCnt});}}}return-1;}intmain(){intn=3;vector<vector<int>>edges={{0,1,1},{1,2,1},{0,2,3}};string labels="aab";intk=1;intresult=shortestPath(n,edges,labels,k);cout<<result<<endl;return0;}