이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 처음에는 백트레킹을 통해 경우의 수를 따져 구하려고 하였지만 다익스트라로 해결할 때에 훨씬 간단하게 해결할 수 있을 것이라는 생각을 중간에 하였고, 다익스트라로 거리를 체크하여 그 중 가장 큰 수를 걸리는 시간으로, 그리고 초기값이 아닌 수를 세어 감염된 컴퓨터의 갯수로 하였다.

Code

import heapq
t=int(input())
def find_computers(c):
    h=[]
    heapq.heappush(h, (0, c))
    dists=[1e9 for _ in range(n+1)]
    dists[c]=0
    while h:
        dist, cur=heapq.heappop(h)
        if dist>dists[cur]:
            continue
        for nxt, time in graph[cur]:
            nxt_time=time+dist
            if dists[nxt]>nxt_time:
                dists[nxt]=nxt_time
                heapq.heappush(h, (nxt_time, nxt))
    return dists
for _ in range(t):
    n, d, c=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))
    answers=find_computers(c)
    answer=0
    cnt=0
    for ans in answers:
        if ans!=1e9:
            answer=max(answer, ans)
            cnt+=1
    print(cnt, answer)