Dijkstra变体多数场景可用，但未知测试用例输出错误求提示

说明 #

这是大学作业，仅需提示而非完整解决方案。

问题要求 #

找到从起点s到终点t的路径，满足路径中边的最大积雪量最小；若存在多条这样的路径，选择总长度最短的。任意两个顶点间最多存在一条边。

输入参数定义 #

n - 顶点数量
m - 边的数量
s - 起点
t - 终点
a - 边的起点列表
b - 边的终点列表
w - 对应边的长度列表
c - 对应边的积雪量列表

尝试实现的代码 #

import heapq

# 交叉点数量, 道路数量, 起点, 终点, 边起点列表, 边终点列表, 长度列表, 积雪列表
def snowy_road(n, m, s, t, a, b, w, c):
    # 初始化所有节点的最大积雪量为无穷大，起点为0
    distancesc = [float("inf")] * n
    distancesc[s-1] = 0
    # 初始化所有节点的总路径长度为无穷大，起点为0
    distancesw = [float("inf")] * n
    distancesw[s-1] = 0

    # 已访问节点集合
    visited = set()

    # 优先队列：(当前路径最大积雪量, 当前路径总长度, 当前节点)
    pq = []
    heapq.heappush(pq, (0, 0, s-1))

    while pq:
        distc, distw, u = heapq.heappop(pq)

        # 节点已处理过则跳过
        if u in visited:
            continue

        visited.add(u)
        # 遍历所有边，找到当前节点的邻接节点
        for i in range(m):
            if a[i] == u+1:
                v = b[i]-1
            elif b[i] == u+1:
                v = a[i]-1
            else:
                continue
            
            # 计算经过当前边后的路径最大积雪量
            altc = max(distc, c[i])
            # 计算经过当前边后的总路径长度
            altw = distw + w[i]

            # 更新条件1：找到更小的最大积雪量
            if altc < distancesc[v]:
                distancesc[v] = altc
                distancesw[v] = altw
                heapq.heappush(pq, (altc, altw, v))
            # 更新条件2：最大积雪量相同，但总长度更短
            elif altc == distancesc[v] and altw < distancesw[v]:
                distancesw[v] = altw
                heapq.heappush(pq, (altc, altw, v))

    # 返回终点的最大积雪量和总路径长度
    return distancesc[t-1], distancesw[t-1]

遇到的问题 #

该Dijkstra变体算法多数场景运行正常，但在某一无法访问的测试用例上输出错误。

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