동까의 코딩

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

문제 풀이/99클럽

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

동까의 코딩 2025. 1. 16. 09:30
반응형

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])

 

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

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

반응형

'문제 풀이 > 99클럽' 카테고리의 다른 글

99클럽 코테 스터디 5일차 TIL  (0) 2025.01.20
99클럽 코테 스터디 4일차 TIL  (0) 2025.01.17
99클럽 코테 스터디 2일차 TIL  (1) 2025.01.14
99클럽 코테 스터디 1일차 TIL  (0) 2025.01.14
[99항해] 39일차 TIL  (0) 2024.06.28