동까의 코딩

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

문제 풀이/99클럽

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

동까의 코딩 2025. 2. 7. 10:38
반응형

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

 

벨만포드 알고리즘에 대해 더 깊게 이해해야될 것 같다.....

아직도 모르는 게 많은 것 같다.

 

import sys

INF= sys.maxsize

def bellman(start):
  global n
  distance = [-INF]*(n+1)
  distance[start]=0
  route= [0]*(n+1)
  result=[]

  for i in range(n):
    for cur_node in range(1, n+1):
      if distance[cur_node]==-INF:
          continue

      for next_node, next_cost in graph[cur_node]:
        if distance[next_node]<distance[cur_node]+next_cost: 
          distance[next_node]=distance[cur_node]+next_cost 
          route[next_node]=cur_node 
          if i==n-1:
            distance[next_node]=INF  
  if distance[n]==INF: 
    print(-1)
    return
  else:
    result.append(n)
    while(n!=1):
      result.append(route[n])
      n= route[n]
    
    result.reverse()
    print(*result)
    return


n,m= map(int, input().split())

graph=[[] for _ in range(n+1)]

for _ in range(m):
  a,b,c= map(int, input().split())
  graph[a].append((b,c))


bellman(1)
반응형

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

99클럽 코테 스터디 TIL  (0) 2025.02.13
99클럽 코테 스터디 TIL  (0) 2025.02.12
99클럽 코테 스터디 TIL 10일차  (0) 2025.02.05
99클럽 코테 스터디 TIL 9일차  (0) 2025.02.04
99클럽 코테 스터디 TIL 8일차  (0) 2025.01.25