BOJ - 10282

백준 문제 링크
해킹

❓접근법

1. 다익스트라 알고리즘을 활용했다.
2. 기본 다익스트라 함수를 distance를 반환하도록 만든다.
3. 문제에서 주어지는 변수를 다 받은 뒤에,
   a가 b에 의존한다는 것은 graph[b].append((a, s))와 같다.
4. 해킹당한 컴퓨터의 번호를 start로 받아주고,
   temp = dijkstra(start)로 저장한다.
   temp에서 INF가 아닌 값을 answer에 저장하고
   answer의 길이와 최댓값을 출력하면 끝!

👌🏻코드

import heapq

INF = int(1e9)

def dijkstra(start):
    
    distance = [INF] * (n + 1) 

    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist , now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for i in graph[now]:

            cost = dist + i[1]

            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

    return distance

T = int(input())

for _ in range(T):
    n, d, start = map(int, input().split())
    
    graph = [[] for _ in range(n + 1)]
    
    for _ in range(d):
        a, b, s = map(int, input().split())
        graph[b].append((a, s))
        
    
    temp = dijkstra(start)
    answer = [i for i in temp if i != INF]
    
    print(len(answer), max(answer))