嗨，咱们一步步拆解这两个场景的实现方法哈——核心思路都是给常规最短路径算法加个状态扩展，来追踪路径长度模k的余数，毕竟普通的最短路只记录到每个节点的最小代价，没法处理模k的约束~

场景二：不含负环的带权图（找s→t、路径长度可被k整除的最廉价路径） #

这是更常见的场景，因为不含负环意味着我们可以用更高效的算法，这里分两种子情况（取决于你对「路径长度」的定义）：

子情况A：路径长度指边的数量（需边数是k的倍数） #

我们把每个节点的状态从单纯的「节点u」扩展成「(u, r)」，其中r是从s到u的路径边数模k的余数。最终要找的就是到达t时余数为0的最小代价，也就是dist[t][0]。

实现步骤：

• 初始化一个二维数组dist，dist[u][r]表示到达节点u、路径边数模k等于r时的最小代价。所有值先设为无穷大，除了dist[s][0] = 0（从s出发到自己，边数为0，模k余0，代价自然是0）。
• 如果图里没有负权边：用Dijkstra算法处理这些状态。每次取出当前代价最小的(u, r)，遍历u的所有邻边u→v（边权为w）。新的余数是r' = (r + 1) % k（因为多走了一条边，边数+1）。如果dist[v][r']比dist[u][r] + w大，就更新它。
• 如果图里有负权边但没负环：用Bellman-Ford算法，迭代V*k次（因为每个节点有k种状态，总状态数是V*k）。每次遍历所有边，对每条边u→v，遍历所有可能的余数r，计算r' = (r + 1) % k，如果dist[v][r']能更小就更新。
• 最后看dist[t][0]，如果还是无穷大，说明不存在满足条件的路径。

子情况B：路径长度指总权值（需总权值模k=0） #

思路和上面几乎一致，只是余数的计算基于路径总权值而非边数：

• 状态还是(u, r)，但r是从s到u的路径总权值模k的余数（注意如果权值是负数，要把余数调整到0~k-1的范围，比如(r + w) % k + k再取模）。
• 初始化dist[s][0] = 0，其余为无穷大。
• 处理边时，对u→v的边权w，新余数是r' = (r + w) % k，调整为非负后更新dist[v][r']。
• 同样用Dijkstra（无负权）或Bellman-Ford（有负权无负环）处理，最终取dist[t][0]。

场景一：任意带权图（含负环）与自然数k #

如果图里存在负环，情况就棘手了——因为负环可以反复绕，既能调整路径的余数，还能无限降低总代价。比如，如果有一个从s能到达、还能走到t的负环，绕环一周的边数（或总权值）模k等于d，那我们可以绕环m次，让总余数凑成0，同时总代价无限变小（这时候就不存在「最廉价」路径了，因为代价能无限低）。

实现步骤：

1. 先按场景二的方法计算dist[t][0]，同时要检测是否存在可达负环：
   • 用Bellman-Ford算法迭代V*k次后，再额外迭代一次。如果这次还能更新某个状态(u, r)，说明存在能到达(u, r)的负环。
2. 检查这个负环是否在s到t的路径上：
   • 确认s能到达这个负环，且负环能到达t。
   • 同时，绕环一周的模k增量d（边数或权值）要满足：存在整数m，使得(当前到t的余数 + m*d) ≡ 0 mod k。简单说就是d和k的最大公约数能整除（0 - 当前到t的余数）。
3. 如果满足上述条件，说明总代价可以无限小，不存在有限的最廉价路径；如果不满足，那dist[t][0]就是答案。

代码示例（场景二子情况B，无负权边） #

用Python实现Dijkstra版本：

import heapq

def cheapest_mod_k_path(graph, node_count, start, end, k):
    # graph: 邻接表，graph[u] = [(v, weight)]
    INF = float('inf')
    # dist[u][r] 记录到达u时，总权值模k余r的最小代价
    dist = [[INF] * k for _ in range(node_count)]
    dist[start][0] = 0
    # 优先队列：(当前总代价, 当前节点, 总权值模k余数)
    heap = []
    heapq.heappush(heap, (0, start, 0))
    
    while heap:
        current_cost, u, remainder = heapq.heappop(heap)
        # 提前终止：找到目标节点且余数为0
        if u == end and remainder == 0:
            return current_cost
        # 跳过已经更新过的旧状态
        if current_cost > dist[u][remainder]:
            continue
        # 遍历所有邻边
        for v, weight in graph[u]:
            new_remainder = (remainder + weight) % k
            # 处理负数余数，确保在0~k-1区间
            if new_remainder < 0:
                new_remainder += k
            new_cost = current_cost + weight
            # 更新状态
            if new_cost < dist[v][new_remainder]:
                dist[v][new_remainder] = new_cost
                heapq.heappush(heap, (new_cost, v, new_remainder))
    
    # 不存在满足条件的路径
    return INF

内容的提问来源于stack exchange，提问作者cstudent1212