전보

p. 262

 

import sys
import heapq

input=sys.stdin.readline

INF=int(1e9)

# 도시의 개수, 통로의 개수, 출발 도시
n, m, c = map(int, input().split())

time=[INF] * (n+1)
graph=[[] for _ in range(n+1)]

for i in range(m):
    # 도시 x부터 도시 y까지 이어지는 통로가 있으며, 전달되는 시간은 z
    x,y,z=map(int, input().split())
    graph[x].append((y,z))

def dijkstra(start):
    q=[]

    heapq.heappush(q, (0, start))

    while q:
        dist, now = heapq.heappop(q)

        if dist > time[now]:
            continue
        else:
            for i in graph[now]:
                cost = dist+i[1]
                if cost < time[i[0]]:
                    time[i[0]] = cost
                    heapq.heappush(q, (cost, i[0]))


dijkstra(c)

count_city = 0
count_time = 0

for i in range(1, n+1):
    if time[i] != INF:
        count_city += 1
        count_time = max(time[i], count_time)
        print(i)

print(count_city, count_time)