CSES 1202 Investigation - Implementation

Track multiple values during Dijkstra:

dist = array, all infinity
cnt = array, all 0
minE = array, all infinity
maxE = array, all 0

dist[1] = 0
cnt[1] = 1
minE[1] = 0
maxE[1] = 0

while pq is not empty:
    (d, u) = pq.pop()
    if d > dist[u]:
        continue
    for (v, w) in adj[u]:
        newD = dist[u] + w
        if newD < dist[v]:
            dist[v] = newD
            cnt[v] = cnt[u]
            minE[v] = minE[u] + 1
            maxE[v] = maxE[u] + 1
            pq.push((newD, v))
        else if newD == dist[v]:
            cnt[v] = (cnt[v] + cnt[u]) mod MOD
            minE[v] = min(minE[v], minE[u] + 1)
            maxE[v] = max(maxE[v], maxE[u] + 1)