[백준] [다익스트라] [heap] 10282. 해킹

10282. 해킹

10282번: 해킹

 

• 내 풀이
  • 다익스트라: heap 써야함 
  • 계속 틀린 이유 
  • 더 짧은 시간값이 나오면 그와 연결된 값들도 다 업데이트 해줘야하므로 힙에 다시 넣어줘야함!!

# a->b 의존 b감염->a감염
import heapq

def bfs(start):
    global result
    global cnt
    visited.add(start)
    result[start]=0
    cnt+=1
    heapq.heappush(q, (0,start))

    while q:
        time, x =heapq.heappop(q)

        for t,g in graph[x]:
            if g not in visited:
                cnt+=1
            visited.add(g)
            if result[g]>time+t:
                result[g] = time + t
                #더 짧은 시간값이 나오면 그와 연결된 값들도 다 업데이트 해줘야하므로
                #힙에 다시 넣어줘야한다
                heapq.heappush(q, (result[g],g))


T = int(input())
for tc in range(T):
    # 컴퓨터수, 의존성 수, 해킹컴 번호(시작)
    n, d, c = map(int, input().split())
    graph = [[] for i in range(n + 1)]
    cnt = 0
    result = [int(1e9) for _ in range(n + 1)]
    visited = set()
    q=[]

    for i in range(d):
        # a->b 의존 s초후 감염
        a, b, s = map(int, input().split())
        graph[b].append((s,a))

    bfs(c)

    tmp = 0
    answer = 0

    # result=[result[i] if i in visited else 0 for i in range(n+1)]

    answer=0
    for r in result:
        if r!=int(1e9):
            answer=max(answer,r)


    print(cnt, answer)