[BUG] - Find Edges in Shortest Paths | O(n*n) solution getting accepted

[RedHeadphone]

LeetCode Username

RedHeadphone

Problem Number, Title, and Link

3123. Find Edges in Shortest Paths https://leetcode.com/problems/find-edges-in-shortest-paths

Bug Category

Missing test case (Incorrect/Inefficient Code getting accepted because of missing test cases)

Bug Description

The solution that I submitted during the contest, has a time complexity of O(n*n) but it got accepted. My Solution used Dijstra to greedily select edges with the least distance from node 0 until it reaches the n-1 node and then it traverses back marking all the edges as part of the shortest path. For the graph like below it is traversing back the same edges again and again.

Language Used for Code

Python/Python3

Code used for Submit/Run operation

class Solution:
    def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]:
        tree = defaultdict(list)
        m = len(edges)
        for ind,(u, v, w) in enumerate(edges):
            tree[u].append((w,v,ind))
            tree[v].append((w,u,ind))

        heap = tree[0]
        heap = [(heap[i][0],heap[i][1],heap[i][2],i) for i in range(len(heap))]

        color_parent = {}
        last_color = len(heap)
        color_map = {i: heap[i][2] for i in range(len(heap))}

        heapify(heap)

        shortest_len = [math.inf]*n
        shortest_len[0] = 0

        color_set = set()

        while heap:
            w, v, i, c = heappop(heap)
            if w>shortest_len[-1]:
                continue
            shortest_len[v] = min(shortest_len[v], w)
            if v==n-1:
                color_set.add(c)
            if shortest_len[v] < w:
                continue
            for w2, v2, i2 in tree[v]:
                if w+w2 < shortest_len[v2]:
                    c2 = last_color
                    last_color+=1
                    color_parent[c2] = c
                    color_map[c2] = i2
                    heappush(heap, (w+w2, v2, i2, c2))

        ans = [False]*m

        for i in list(color_set):
            while i in color_parent:
                i = color_parent[i]
                color_set.add(i)

        indexes = [color_map[i] for i in color_set]
        for i in indexes:
            ans[i] = True

        return ans

Expected behavior

This solution was expected to give me a Time Limit Exceeded, but it was accepted. I generated a test case that gives TLE, I have attached the python script and the test case below.

Test gen python script:

n = 12_502 + 25_000
edges_count = 50_000
last = n-1 
junction = n-2
curr = n-3
edges = []
for i in range(12_500):
    u,v,w = curr,last,1
    edges.append([u,v,w])
    u,v,w = curr,junction,1
    edges.append([u,v,w])
    curr-=1
to_connect = junction
while curr >= 0:
    u,v,w = curr,to_connect,1
    edges.append([u,v,w])
    to_connect = curr
    curr-=1
with open('input.txt', 'w') as f:
    print(n, file=f)
    print(edges, file=f)
verify = True
for u,v,w in edges:
    if u==v or not (0<=u<n) or not (0<=v<n):
        verify = False
print(n,len(edges),edges_count,verify)

test case: input.txt

Screenshots

Additional context

No response

[exalate-issue-sync[bot]]

Joyce_Ndisya commented: Hello,

Your reported issue has been relayed to our team for thorough investigation. We appreciate your patience as we work to address and resolve this matter. We will reach out to you when we have updates regarding the issue.

If you have any further questions or concerns in the meantime, please feel free to let us know.

Best regards, LeetCode Support Team

[exalate-issue-sync[bot]]

Joyce_Ndisya commented: Thank you for your time.

Your feedback has been used to enhance the problem. As a token of our appreciation, your LeetCode account has been credited with 100 LeetCoins.

If you have any more questions or additional feedback, please don't hesitate to let us know. Your continued support is invaluable to us!

Best regards, The LeetCode Team