支持单次边权整除操作的Dijkstra算法改进咨询

所有调整围绕「单次边权整除机会的消耗状态」设计，整体复杂度和标准Dijkstra同级，完全适配题目给出的节点、边数规模约束。

具体调整点 #

• 重构状态定义
  原Dijkstra用一维数组dist[u]存储起点到u的最短路径，调整后拆分为两层独立的距离记录：
  • dist0[u]：从1走到u的路径上，从未使用过边权整除操作的最短距离
  • dist1[u]：从1走到u的路径上，已经用完唯一一次边权整除操作的最短距离
    初始化仅设置dist0[1] = 0，其余所有dist0、dist1值设为无穷大。
• 调整优先队列元素结构
  原优先队列仅存储(当前路径长度, 节点)，调整后新增“整除操作使用状态”标记，入队格式为(当前路径长度, 节点, 状态值)：状态值为0代表当前路径未消耗整除机会，为1代表已消耗。
• 重写松弛分支逻辑
  遍历邻接边时，必须匹配当前节点的状态值做对应松弛，不能遗漏合法路径：
  1. 若当前节点来自状态0（未用整除机会），对邻边u->v（边权w）存在两种合法走法：
     • 不使用整除机会走边：若dist0[u] + w < dist0[v]，则更新dist0[v]，把(dist0[v], v, 0)入队
     • 对当前边用掉唯一一次整除机会：边权取整数整除结果w // k，若dist0[u] + (w // k) < dist1[v]，则更新dist1[v]，把(dist1[v], v, 1)入队
  2. 若当前节点来自状态1（已用完整除机会），对邻边u->v（边权w）仅有一种合法走法：
     • 无剩余整除机会，正常累加边权：若dist1[u] + w < dist1[v]，则更新dist1[v]，把(dist1[v], v, 1)入队
• 修正结果取值规则
  原算法直接取终点N的dist值作为结果，调整后需要同时对比两个状态下到N的最短距离，取最小值作为最终答案，即min(dist0[N], dist1[N])。

示例匹配验证 #

以题目给出的N=4、K=3的示例场景为例，算法执行时，从状态0的节点2出发，对边2-4使用整除操作（190//3=63），得到到节点4的状态1距离为70+63=133，对比其他到4的路径（无操作的1-2-4总长260、1-3-4总长448），最终取到的最小值133和示例结果完全匹配。

复杂度说明 #

调整后总状态数为2N，单条边的松弛分支最多为原逻辑的2倍，整体运行复杂度为O(M + N log N)，完全适配N≤1e5、M≤2e5的规模要求，不存在运行超时问题。

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