10282

날짜 : 2022. 12. 10

사용 언어 : python

 

문제

 

 

코드

import sys
import heapq

t = int(sys.stdin.readline())  # 테스트케이스
INF = int(1e9)


def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dist[start] = 0
    while q:
        d, now = heapq.heappop(q)  # now까지의 길이, 현재노드(now)
        if d > dist[now]: continue  # 이미 확인완료
        for i in graph[now]:
            cost = d + i[1]
            if cost < dist[i[0]]:
                dist[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    return


for _ in range(t):
    n, d, c = map(int, sys.stdin.readline().split())  # 노드 개수, 엣지 개수, 해킹당한 컴퓨터(start)
    graph = [[] for i in range(n + 1)]
    dist = [INF] * (n + 1)
    for _ in range(d):
        a, b, s = map(int, sys.stdin.readline().split())  # 도착, 시작, cost
        graph[b].append((a, s))  # 시작노드에 대한 (도착점, cost)
    dijkstra(c)
    cnt, time = 0, 0
    for i in dist:
        if i == INF: continue
        cnt += 1
        time = max(time, i)
    print(cnt, time)
    #print(dist)

 

 

풀이

- 다익스트라를 활용한 풀이이다.

 

 

 

알게된 점

- 이번엔 이전 다익스트라 알고리즘을 참고하지 않고 풀이했다.

 

 

참고 사이트

-