Dijkstra variation works most of the time, but gives wrong output on a test that I do not have access to

Question

first of all let me pretext this by the fact that this is for an university homework, so I only want hints and not solutions.

The problem consists of finding the path from s to t that has the smallest maximum amount of snow on one of the edges, while choosing shortest distance for tie breaking. (i. e. if multiple edges with the same snow amount are considered, we take the one with the shortest length). For any two vertices, there is at most one edge that connects them.

n - number of vertices
m - number of edges
s - source
t - target
a - list of edge beginnings
b - list of edge ends
w - list of lengths corresponding to the edges
c - list of amounts of snow corresponding to the edges

I would really appreciate the help as I've been racking my head over this for a long time.

I tried this.

import heapq

# # intersections, # roads, start list, end list, len list, snow list
def snowy_road(n, m, s, t, a, b, w, c):
    # Initialize distances to all nodes as infinite except for the source node, which has distance 0
    distancesc = [float("inf")] * n
    distancesc[s-1] = 0
    distancesw = [float("inf")] * n
    distancesw[s-1] = 0

    # Create a set to store the nodes that have been visited
    visited = set()

    # Create a priority queue to store the nodes that still need to be processed
    # We will use the distance to the source node as the priority
    # (i.e. the next node to process will be the one with the smallest distance to the source)
    pq = []
    pq.append((0, 0, s-1))

    while pq:
        # Pop the node with the smallest distance from the priority queue
        distc, distw, u = heapq.heappop(pq)

        # Skip the node if it has already been visited
        if u in visited:
            continue

        # Mark the node as visited
        visited.add(u)
        # Update the distances to all adjacent nodes
        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 = c[i]
            if distc != float("inf"):
                altc = max(distc, altc)
            altw = distw + w[i]
            if altc < distancesc[v]:
                distancesc[v] = altc
                distancesw[v] = altw
                heapq.heappush(pq, (altc, altw, v))
            elif altc == distancesc[v] and altw < distancesw[v]:
                distancesw[v] = altw
                heapq.heappush(pq, (altc, altw, v))

           

    # Return the distance to the target node
    return distancesc[t-1], distancesw[t-1]

Answer 1

If anyone is wondering, I solved this using two consequent Dijkstras. The first one finds the value of the shortest bottleneck path, the second one takes this value into account and doest a shortest path normal Dijkstra on the graph using w, while considering only edges that have a snow coverage <= than the bottleneck we found. Thank you to everyone that responded!