99클럽 코테 스터디 3일차 TIL

https://www.acmicpc.net/problem/2211

 

import sys,heapq
input=sys.stdin.readline
INF=int(1e9)

def move():

    dp[1]=0
    heap=[] ; heapq.heappush(heap , (0,1))

    while heap:

        value,node=heapq.heappop(heap)

        if dp[node]<value:
            continue

        for next_value,next_node in graph[node]:

            next_value+=value

            if next_value<dp[next_node]:
                dp[next_node]=next_value
                check[next_node]=node
                heapq.heappush(heap, (next_value , next_node))


N,M=map(int,input().split())

graph=[ [] for _ in range(N+1) ]
dp=[INF]*(N+1)
check=[0]*(N+1)

ALL=[]
for i in range(M):
    A,B,C=map(int,input().split())
    graph[A].append((C,B))
    graph[B].append((C,A))

    ALL.append((A , B))

move()
print(N-1)
for i in range(2,N+1):
    print(i , check[i])

 

다익스트라 알고리즘을 사용한 풀이를 참조했고, 모르고 있던 알고리즘이라 공부를 해보았습니다.

오늘의 문제가 나오기 전에 또 풀어볼 예정입니다.