전보 (파이썬) / 최단경로(다익스트라)

문제

• 어떤 나라에 N개의 도시가 있다.
• X에서 Y로 향하는 통로가 있으면 X->Y는 보낼 수 있지만 Y->X로는 따로 통로가 있어야 한다. 
• 특정 도시에서 다른 도시로 전부 전보를 보내기 위해서 필요한 시간은 얼마인지 계산하라.

 

입력

• 첫째 줄에 도시의 개수 N, 통로의 개수 M, 메세지를 보내고자 하는 도시 C가 주어진다.
• (1<= N <= 30000 , 1<= M <= 200000, 1<= C <= N)
• 둘째 줄부터 M+1 번째 줄에 걸쳐서 통로에 대한 정보 X,Y,Z가 주어진다. 이는 특정 도시 X에서 다른 특정 도시 Y로 이어지는 통로가 있으며, 메세지가 전달되는 시간이 Z라는 의미다.
• (1<=X, Y<=N, 1<=Z<=1000)

 

출력 

• 첫째 줄에 도시 C에서 보낸 메세지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분하여 출력한다.

"INPUT"
3 2 1
1 2 4
1 3 2

"OUTPUT"
2 4

---

풀이

해당 문제는 C로부터 갈 수 있는 모든 최단 경로를 구해서 가장 긴 경로를 출력하면 된다.

이 때 "한 지점에서 특정 지점까지 최단 경로를 구하는 알고리즘" 인 다익스트라로 접근하면 된다.

heap을 통해 구현하여 시간복잡성 보완하기.

 

import heapq
import sys
INF = int(1e9)

sys.stdin = open("input_9-3.txt", "r")
sys.stdout = open("output_9-3.txt","w")

# input
n, m ,c  = map(int, input().split())
graph_ll = [[] for _ in range(n+1)]
q = []
dist = [INF] * (n+1)

# input 처리
for _ in range(m):
    src, dst, cost = map(int, input().split())
    graph_ll[src].append((dst, cost))

# 초기값 heap 튜플(dst, cost) 순
heapq.heappush(q, (c, 0))
dist[c] = 0

# 다익스트라 최단경로 from c
while q :
    dst , cost = heapq.heappop(q)
    # 더 작으면 넘어가기
    if dist[dst] <  cost:
        continue

    # dst를 거쳐 갈 수 있는 곳 갱신
    for l in graph_ll[dst]:
        dst_dst = l[0]
        dst_cost = l[1]

        # 더 작은 값 갱신 (기존값 vs  dst 거쳐가는 값)
        if dist[dst_dst] > (cost + dst_cost):
            dist[dst_dst] = cost + dst_cost
            heapq.heappush(q, (dst_dst, cost + dst_cost))

# return
cnt = 0
for idx, d in enumerate(dist):
    if d == INF:
        dist[idx] = -1

    if dist[idx]!= 0 and dist[idx] != -1:
        cnt +=1


print(cnt, max(dist))