[이것이 코딩테스트다] 전보 문제

p263

전보 문제

# 이코테 p262
# 전보
import sys
import heapq
INF = int(1e9)
n, m, c = map(int, sys.stdin.readline().split())
graph = [[] for i in range(n+1)]
for _ in range(m):
    x, y, z = map(int,sys.stdin.readline().split())
    graph[x].append((y,z))
distance = [INF] * (n+1)

def dijkstra(start):
    q = []
    # 시작 노드로 가기위한 최단 경로 0
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            y, z = i[0], i[1] #y가 노드 z가 비용
            cost = dist + z
            if cost < distance[y]:
                distance[y] = cost
                heapq.heappush(q, (cost, y))
dijkstra(c)
cnt = 0
max_distance = 0
for d in distance:
    if d != INF:
        cnt += 1
        max_distance = max(max_distance, d)
print(cnt-1, max_distance)