동빈북 최단거리 전보 파이썬

문제

어떤 나라에 N개의 도시가 있다.

X에서 Y로 향하는 통로가 있으면 X->Y는 보낼 수 있지만 Y->X로는 따로 통로가 있어야 한다. 

C에서 보낸 메세지를 받게 되는 도시의 총 개수와 도시들이 모두 메세지를 받는데까지 걸리는 시간은 얼마인지 

계산하는 프로그램 작성

 

입력

첫째 줄에 도시의 개수 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에서 보낸 메세지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분하여 출력한다.

 

 

 

n,m이 커서 다익스트라를 사용하기로 했다.

구하는건 다익스트라를 통해서 최단거리 테이블을 완성한 후에 INF가 아닌 도시의 개수를 세고,

모두 받는 시간은 총합이라고 생각해서 풀었다.

 

그러나 도시의 개수에서는 자기자신은 뺐어야 했고,

총합이 아니라 INF를 제외한 가장 큰 수였다. 왜냐하면 가장 큰시간동안 나머지는 다 보낼 수 있기 때문이다.

 

기억해야 할 부분은 그래프배열에 노드들의 정보를 집어 넣을 때 튜플의 형태로(다음노드, 거리) 이렇게 집어넣었고,

우선순위 큐에서는 (거리, 다음노드)로 집어넣었다. 최소힙에서는 튜플의 첫번째 원소로 정렬하기 때문이다.

 

다익스트라의 핵심 알고리즘은

가장 짧은 거리의 노드를 pop해서 이미 최단거리 테이블이 최소가 아니라는 가정하에 새로운 최단거리를 구한다.

현재 뽑은 노드의 거리 + 인접한 노드들각각의 거리가 새로운 최단 거리다.( 이 때 인덱스를 조심해야 한다. 0인지 1인지)

 

그다음에 이 최단거리와 최단거리 테이블의 인접노드 거리값과 비교해서 계속 갱신해주면 된다.

 

 

나머지는 최단거리 테이블에서 어떻게 출력을 뽑아낼까의 문제만 남는다.

 

 

import sys
import heapq
input=sys.stdin.readline
INF=int(1e9)#무한 값 의미

# 노드의 개수, 간선의 개수, 시작노드 입력받기
n,m,c=map(int,input().split())

#각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기
graph=[[] for _ in range(n+1)]

#최단거리 테이블 무한으로 초기화
distance=[INF]*(n+1)

#모든 간선 정보 입력받기.
for i in range(m):
    x,y,z=map(int,input().split())
    graph[x].append((y,z)) # x번 노드에서 y번 노드로 이동하는데 비용이 z라는 의미.  ( 다음노드, 비용)의 형태로 입력.

def dijkstra(start):
    q=[]
    heapq.heappush(q,(0,start))#시작노드를 가기위한 거리는 0으로 설정. ( 거리, 다음노드) 첫번째원소로 정렬되는 최소힙을 이용하려고 비용을 첫번쨰원소로 둠,
    distance[start]=0

    while q:#큐에 원소가 존재할 때까지
        #가장 거리가 짧은 노드에 대한 정보 꺼내기
        dist,now=heapq.heappop(q)
        if distance[now]<dist:
            continue
        #현재노드와 인접한 모든 노드들을 확인한다.
        for i in graph[now]:
            cost=dist+i[1] #cost=현재 노드거리 + 인접노드의 거리  graph 에는 (다음도시, 거리) 이렇게 삽입했음.
            #현재노드를 거쳐서 다른노드로 이동하는 거리가 더 짧은 경우에
            if cost<distance[i[0]]:
                distance[i[0]]=cost #갱신
                heapq.heappush(q,(cost,i[0])) #큐에 추가
dijkstra(c)
print(distance)
cnt=0 #도달 가능한 도시 개수
max_distance=0#도달가능한 노드중 가장 멀리있는 노드의 최단거리
for d in distance:
    if d!=INF and d!=0 :
        cnt+=1
        max_distance=max(max_distance, d)
print(cnt,max_distance,end=' ')