[다익스트라] 전보 (python)

전보 - 이코테 교재 p262

 

문제설명

 

어떤 나라에는 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에서 보낸 메세지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분해 출력한다.

 

POINT

: 시작노드에서 모든 노드들까지의 최단 거리 구하기 (다익스트라)

 

다익스트라 기본 문제라 따로 정리해봤다.

새 노드를 거쳐서 가는 경로가 더 최단일 경우 업데이트해주기!

 

 

import heapq
n, m, c = map(int, input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
    x, y, cost = list(map(int, input().split()))
    graph[x].append((y, cost))

dist = [1e9] * (n+1)
dist[c] = 0
q = []
heapq.heappush(q, (0, c))

while q:
    now_cost, now = heapq.heappop(q)
    if dist[now] < now_cost:  # 이미 저장되어 있는 거리가 더 최단일 경우 패스!
        continue
    for next in graph[now]:
        next_node, next_cost = next
        if now_cost + next_cost < dist[next_node]:
            dist[next_node] = now_cost + next_cost
            heapq.heappush(q, (dist[next_node], next_node))

result = 0
cnt = 0
for i in range(n):
    if dist[i] == 1e9:
        continue
    cnt += 1
    if result < dist[i]:
        result = dist[i]

print(cnt, result)