[HackerRank][Python3] Dijkstra: Shortest Reach 2

Problem :

https://www.hackerrank.com/challenges/dijkstrashortreach/problem

My Solution :

#!/usr/bin/env python3

from collections import deque


def shortestReach(n, edges, s):
    INF = float('Inf')

    graph = [[INF]*(n+1) for _ in range(n+1)]
    for u, v, cost in edges:
        graph[u][v] = min(graph[u][v], cost)
        graph[v][u] = graph[u][v]

    distances = [INF]*(n+1)
    distances[s] = 0

    queue = deque()
    queue.append(s)
    while queue:
        node = queue.popleft()
        for v in range(n+1):
            cost = graph[node][v]
            if cost != INF:
                if distances[node] + cost < distances[v]:
                    distances[v] = distances[node] + cost
                    queue.append(v)

    result = []
    for d in distances[1:]:
        if d not in (INF, 0):
            result.append(d)
        elif d == INF:
            result.append(-1)

    return ' '.join(map(str, result))


t = int(input())
for _ in range(t):
    n, m = map(int, input().split())
    edges = set()
    for _ in range(m):
        edges.add(tuple(map(int, input().strip().split())))
    s = int(input())
    result = shortestReach(n, edges, s)
    print(result)

Comment :

마지막 Testcase 7번이 Timeout 나길래 edges를 input으로 받을 때 list()에 넣지 않고 set()에 넣었다. 왜냐하면 엄청나게 많은 중복 값이 입력으로 들어오기 때문이다. 그걸 일일이 graph에 넣다보면 timeout 발생할 수 밖에 없다. (300만 이상 라인이 들어오는데 유니크한 라인은 4000라인 미만)