[파이썬] [최단경로] 전보

문제설명

어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메세지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메세지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내려면 도시 X -> Y로 가는 통로가 설치되어 있어야 한다. 어느 날 C라는 도시 C에서 위급 상황이 발생해 최대한 많은 도시로 전보를 보내야 한다. 메세지는 도시 C에서 출발해 각 도시 사이에 설치된 통로를 거쳐 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 정보로 주어졌을 때, 도시 C에서 보낸 메세지를 받게 되는 도시의 개수는 총 몇 개 이며 도시들이 모두 메세지를 받는 데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성해라.

입력조건

• 첫째 줄에 도시의 개수 N, 통로의 개수 M, 메세지를 보내고자 하는 도시 C가 주어진다.(1<= N <= 30,000 , 1 <= M <= 200,000 , 1 <= C <= N)
• 둘째 줄부터 M+1 번째 줄에 걸쳐서 통로에 대한 정보 X, Y, Z가 주어진다. 이는 특정 도시 X에서 다른 특정 도시 Y로 이어지는 통로가 있으며, 메세지가 전달되는 시간이 Z라는 의미다.(1 <= X, Y <= N , 1 <= Z <= 1,000)

출력조건

• 첫째 줄에 도시 C에서 보낸 메세지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분해 출력한다.

코드

import heapq

n, m, c = map(int, input().split())
INF = 1001
distance = [INF] * (n+1)
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y, z = map(int, input().split())
    graph[x].append((y, z))
# 시작노드(c) 처리
q = []
distance[c] = 0
heapq.heappush(q, (0, c))
while q:
    dist, node = heapq.heappop(q)
    if dist > distance[node]:
        continue
    for next in graph[node]:
        cost = distance[node] + next[1]
        if cost < distance[next[0]]:
            distance[next[0]] = cost
            heapq.heappush(q, (cost, next[0]))

count = 0
max_dist = 0
for d in distance:
    if d != INF:
        count += 1
        max_dist = max(max_dist, d)

print(count-1, max_dist)