[이코테] 최단경로 문제 3 [전보] 파이썬 풀이

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(1000000)
import heapq

INF = int(1e9)
N,M,C = map(int,sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
distance = [INF] * (N+1)
for i in range(M):
    x,y,z = map(int,sys.stdin.readline().split())
    graph[x].append((y,z))

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

dijkstra(C)
count = 0
max = -1
for i in distance:
    if i!= INF and i!=0:
        count +=1
    if i > max and i < INF:
        max = i

print(count,max,end='')

걸리는 총 시간 = 메시지는 동시에 송신하므로 시간중 가장 오래 걸리는 Max값을 찾아주면 되고

받는 도시는 , 자기 자신과 INF가 되지 않는, 즉 distance[i]의 원소 중에서 0과 INF가 아니라면 

i번째 도시에 도달할 수 있다는 의미가 된다.