[Dijkstra] 메시지 보내기

문제

N개의 도시가 있고 각 도시에서 메시지를 다른 도시로 보낼 수 있다.

도시간의 도로는 양방향이 아니고 일방향이다

도로를 가는 데에는 일정 시간이 소모된다

C라는 도시에서 메세지를 보낼 때, 최대한 많은 도시에 보내려고 한다면

메시지를 받는 조시의 개수는 총 몇개이며 도시들이 모두 메시지를 받는 데까지 걸리는 시간은?

1<N<30000  1<M<200000

 

한점에서 다른 점들까지의 가는 거리의 시간을 묻고 있으므로 

N과 M의 크기가 굉장히 크기 때문에 특정 점에서 다른점까지 가는 거리를 찾는 다익스트라 중에서

우선순위 큐를 사용한다

 

• 시작점에서 시작점 외의 도시들까지 direct로 연결된 것을 우선순위 큐에 넣는다
• 가장 최단 거리를 가진 노드를 우선순위 큐에서 꺼내어 (logn으로 알아서 최단 거리 노드가 나옴)
• 최단거리까지의 최단거리 + 다른 direct로 연결된 노드와의 거리가 원래 distance값보다 작으면 넣는다
• 그리고 direct 연결된 노드와 cost값을 우선순위 큐에 넣는다

import sys
import heapq
input = sys.stdin.readline


INF = int(1e9)

N, M, C = map(int, input().split())

graph = [[] for i in range(0, N+1)]
distance = [INF] * (N+1)


for _ in range(0, M):
    X, Y, Z = map(int, input().split())
    graph[X].append((Y, Z))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, city = heapq.heappop(q)
        if distance[city] > dist:
            continue
        for i in graph[city]:
            cost = dist + i[1]
            if cost<distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
    
dijkstra(C)

cnt = 0
time = 0

for i in range(1, N+1):
    if distance[i] != INF and i!=C:
        cnt +=1
        time = max(time, distance[i])

print(distance)
print(cnt, time)