Chapter 09 최단 경로 - 전보

https://www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

[262p 전보]

 

import sys
import heapq

INF = int(1e9)

n, m, c = map(int, sys.stdin.readline().rstrip().split())
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)

# 단방향, 거리 비용 cost
for _ in range(m):
    a, b, cost = map(int, sys.stdin.readline().rstrip().split())
    graph[a].append((b, cost))


# 데이크스트라
def dijkstra(start):
    queue = []
    heapq.heappush(queue, (0, start))
    distance[start] = 0

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

        if distance[now] < dist:
            continue

        for v, c in graph[now]:
            cost = dist + c

            if distance[v] > cost:
                distance[v] = cost
                heapq.heappush(queue, (cost, v))

dijkstra(c)

# 도달할 수 있는 노드의 개수
count = 0
# 도달할 수 있는 거리 중 최대 비용
time = 0

for dist in distance:
    # 경로가 없거나, 시작 노드인 경우 제외 (거리 비용이 1 이상이므로)
    if dist != INF and dist != 0:
        count += 1
        time = max(time, dist)

print(count, time)