[dijkstra] 백준 10282 해킹

답이 맞긴한데 시간초과..

시간초과
import sys
from collections import deque

T = int(sys.stdin.readline())

def infection(graph, c, n):
    time = [sys.maxsize]*(n+1)
    time[c]=0
    q = deque()
    q.append(c)
    while q:
        p = q.popleft()
        for i, w in graph[p]:
            time[i] = min(time[i], time[p]+w)
            if i not in q:
                q.append(i)
    cnt = 0
    ans = 0
    for t in time:
        if t != sys.maxsize:
           cnt+=1
           ans = max(ans, t)
    print(cnt, ans)
for _ in range(T):
    n, d, c = map(int, sys.stdin.readline().split())
    graph = {i:[] for i in range(n+1)}
    for _ in range(d):
        a, b, s = map(int, sys.stdin.readline().split())
        graph[b].append([a,s])
    infection(graph, c, n)

 

 

힙을 이용해 성공

import sys
import heapq

def dijkstra(graph, c, n):
    distances = [sys.maxsize]*(n+1)
    heap = [[0, c]]
    distances[c]=0
    while heap:
        current_distance, current_idx = heapq.heappop(heap)
        for next_idx, next_distance in graph[current_idx]:
            distance = current_distance + next_distance
            if distances[next_idx]>distance:
                distances[next_idx]=distance
                heapq.heappush(heap, [distance, next_idx])
    cnt = 0
    ans = 0
    for d in distances:
        if d != sys.maxsize:
           cnt+=1
           ans = max(ans, d)
    print(cnt, ans)
        
T = int(sys.stdin.readline())
for _ in range(T):
    n, d, c = map(int, sys.stdin.readline().split())
    graph = {i:[] for i in range(n+1)}
    for _ in range(d):
        a, b, s = map(int, sys.stdin.readline().split())
        graph[b].append([a,s])
    dijkstra(graph, c, n)

 

 

다익스트라를 구현하는 방법

• 우선순위 큐
• 리스트
  • O(n**2)

 

https://doing7.tistory.com/76

[알고리즘] 다익스트라 최단경로 with Python