2026-09-27：最多 K 个连续相同字符的最短路径。用go语言，有一个包含 n 个节点的有向图，节点编号为 0 到 n-1。图中的边由 edges 给出，

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。

大体步骤如下：

1. 理解路径标签限制
路径从节点 0 出发，依次经过若干节点，最终到达节点 n-1。
每经过一个节点，就把该节点的 labels 字符拼接到路径字符串末尾。
要求这个字符串中，任意一种字符连续出现的次数不能超过 k。
注意：连续相同字符只和相邻节点标签有关。
如果当前节点标签和下一个节点标签相同，那么连续计数加一；如果不同，连续计数重新变成 1。
起点节点的标签也要算进去，所以起点本身的连续计数初始为 1。

2. 建图
根据 edges 建立有向图的邻接表。
对于每条边 [u, v, w]，表示从 u 到 v 有一条权重为 w 的有向边。
后续从某个节点扩展时，就遍历它的所有出边。

3. 定义状态
状态需要包含两部分信息：
第一，当前所在节点 x。
第二，到达 x 时，路径末尾连续相同标签的数量 cnt。
对于每个状态，需要记录从起点 0 到当前节点 x，并且末尾连续计数为 cnt 时的最小总边权。
因此使用一个二维距离表：
dis[x][cnt] 表示到达节点 x，且末尾连续相同字符数为 cnt 时的最小边权和。
其中 cnt 的取值范围是 1 到 k，因为一旦超过 k 就不合法，不需要继续考虑。

4. 初始化
所有 dis[x][cnt] 初始化为无穷大，表示暂时不可达。
起点是节点 0。
起点本身有一个标签，所以它自己的末尾连续相同字符数为 1。
因此 dis[0][1] = 0。
然后把状态 (当前总边权 0, 当前节点 0, 当前连续计数 1) 放入优先队列。
优先队列按照当前总边权从小到大排序，这就是 Dijkstra 算法的基础。

5. 使用优先队列进行最短路扩展
只要优先队列不为空，就重复以下过程：
第一，从优先队列中弹出当前总边权最小的状态。
这个状态包含：当前距离 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，并把新状态放入优先队列。

6. 无法到达终点时
如果优先队列一直处理到空，都没有在弹出时遇到终点 n-1，说明不存在满足标签限制的路径。
此时返回 -1。

7. 结合示例理解
题目示例中：
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。

8. 为什么需要二维距离表
如果只记录到达某个节点的最小距离，而不记录末尾连续相同字符数，可能会丢失信息。
例如到达同一个节点时，距离较大但末尾连续计数较小的路径，后续可能还能继续走；而距离较小但末尾连续计数较大的路径，后续可能因为超过 k 而不能走。
所以必须把“节点 + 末尾连续计数”作为一个完整状态来做最短路。

9. 正确性要点
图中所有边权都是正数，因此可以使用 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完整代码如下：

package main

 import (
    "container/heap"
    "fmt"
    "math"
)

 func shortestPath(n int, edges [][]int, labels string, k int)int {
    type edge struct{ to, w int }
    g := make([][]edge, n)
    for _, e := range edges {
        x, y, w := e[0], e[1], e[2]
        g[x] = append(g[x], edge{y, w})
    }

     dis := make([][]int, n)
    for i := range dis {
        dis[i] = make([]int, k+1)
        for j := range dis[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.cnt
        if x == n-1 {
            return d
        }
        if d > dis[x][cnt] {
            continue
        }
        for _, e := range g[x] {
            y := e.to
            newCnt := 1
            if labels[y] == labels[x] {
                newCnt = cnt + 1
            }
            newDis := d + e.w
            if newCnt <= k && newDis < dis[y][newCnt] {
                dis[y][newCnt] = newDis
                heap.Push(&h, tuple{newDis, y, newCnt})
            }
        }
    }

     return-1
}

 // 最短路长度, 节点编号, 最后连续相同字母个数
type tuple struct{ dis, x, cnt int }
type hp []tuple

 func (h hp) Len() int           { returnlen(h) }
func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
func (h hp) Swap(i, j int)      { 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 }

 func main() {
    n := 3
    edges := [][]int{{0, 1, 1}, {1, 2, 1}, {0, 2, 3}}
    labels := "aab"
    k := 1
    result := shortestPath(n, edges, labels, k)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 import heapq
import math

 def shortestPath(n, edges, labels, k):
    # 建图
    g = [[] for _ in range(n)]
    for u, v, w in edges:
        g[u].append((v, w))

     INF = math.inf

     # dist[i][c] 表示到达节点 i 时，末尾连续相同标签数量为 c 的最小边权和
    dist = [[INF] * (k + 1) for _ in range(n)]

     if k < 1:
        return-1

     # 起点为节点 0，初始连续相同标签数量为 1
    dist[0][1] = 0

     # 优先队列元素：(当前总权重, 当前节点, 当前末尾连续相同标签数量)
    pq = [(0, 0, 1)]

     while pq:
        d, x, cnt = heapq.heappop(pq)

         if d > dist[x][cnt]:
            continue

         # 第一次弹出终点时，即为最小总边权
        if x == n - 1:
            return d

         for y, w in g[x]:
            if labels[y] == labels[x]:
                new_cnt = cnt + 1
            else:
                new_cnt = 1

             new_dis = d + w

             if new_cnt <= k and new_dis < dist[y][new_cnt]:
                dist[y][new_cnt] = new_dis
                heapq.heappush(pq, (new_dis, y, new_cnt))

     return-1

 if __name__ == "__main__":
    n = 3
    edges = [[0, 1, 1], [1, 2, 1], [0, 2, 3]]
    labels = "aab"
    k = 1

     result = shortestPath(n, edges, labels, k)
    print(result)

C++完整代码如下：

  

using namespace std;

 struct State {
    int d, x, cnt;
    bool operator>(const State& other) const {
        return d > other.d; // 小顶堆
    }
};

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

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。