문제

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100개이다. 각 테스트 케이스는 다음과 같이 이루어져 있다.

첫째 줄에 컴퓨터 개수 n, 의존성 개수 d, 해킹당한 컴퓨터의 번호 c가 주어진다(1 ≤ n ≤ 10,000, 1 ≤ d ≤ 100,000, 1 ≤ c ≤ n).
이어서 d개의 줄에 각 의존성을 나타내는 정수 a, b, s가 주어진다(1 ≤ a, b ≤ n, a ≠ b, 0 ≤ s ≤ 1,000). 이는 컴퓨터 a가 컴퓨터 b를 의존하며, 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다.
각 테스트 케이스에서 같은 의존성 (a, b)가 두 번 이상 존재하지 않는다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.

입력 예시 1

2
3 2 2
2 1 5
3 2 5
3 3 1
2 1 2
3 1 8
3 2 4

출력 예시 1

2 5
3 6

문제 이해

다익스트라 기본 구현 문제인데 distance 리스트를 활용해야 한다. DFS 문제는 활용으로 넘어가면 좀 생각할 게 많은데, 이번 문제는 그정도는 아니다.

결과값으로 몇개의 노드에 방문했는지, 가장 최단거리가 큰 값은 얼마인지 출력한다. 전자는 distance리스트를 1부터 n+1까지 돌면서 INF가 아닌 것을 count하고 출력하면 되고, 후자는 마찬가지로 돌면서 INF가 아니면서 가장 큰 값을 출력하면 된다.

코드

# 백준 10282번 해킹

# 읽는 속도 효율화
import sys
input = sys.stdin.readline

# Import PriorityQueue
from queue import PriorityQueue

def Dijkstra(cur_time, start_node):

    time = [INF] * (n+1)

    pq = PriorityQueue()
    pq.put([cur_time, start_node])
    time[start_node] = 0

    while not pq.empty():

        cur_time, cur_node = pq.get()

        if cur_time > time[cur_node]: # 어차피 갱신되지 않을 값이 반복문을 돌지 않도록 방지
            continue

        for adj_node, adj_time in adj_list[cur_node]:
            temp_time = cur_time + adj_time
            if temp_time < time[adj_node]:
                time[adj_node] = temp_time
                pq.put([temp_time, adj_node])
    return time

# 0. 테스트 케이스 횟수
T = int(input())

for i in range(T):

    # 1. 입력 및 초기화
    n, d, start_node = map(int, input().split())
    INF = int(1e12)
    
    # 2. Create adj_list
    adj_list = [[] for _ in range(n+1)] # 노드 번호가 1부터터
    for i in range(d):
        a, b, s = map(int, input().split())
        adj_list[b].append([a, s])

    # 3. Excute Dijkstra Algorithm
    time_list = Dijkstra(0 , start_node) # cur_time, start_node

    # 4. Print result
    count = 0
    max_time = 0
    for i in range(1, n+1):
        if time_list[i] != INF:
            count += 1

        # 값이 INF면 방문할 수가 없는 곳이니까 걸러준다.
        if time_list[i] > max_time and time_list[i] != INF:
            max_time = time_list[i]
        
    
    print(count, end=" ")
    print(max_time)