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

버스타고 도시 가는데 시간역행이 일어나기도 한다. 이 때 1번 도시에서 나머지 도시로 가는 최단거리를 구하는 문제이다.

https://velog.io/@user_anomalee/BOJ-1865-%EC%9B%9C%ED%99%80

웜홀 문제에서 비슷하게 접근했던 것이 생각이 났는데 구체적으로 어떻게 했는지 기억이 안 나서 참고하며 풀었다.

Python

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

bus = [list(map(int, input().split())) for _ in range(m)]
max_cost = 500 * 6000 * 30000

dp = [max_cost] * (n+1)
dp[1] = 0

chk = False

for i in range(1, n+1):
  for a, b, c in bus:
    if dp[a] == max_cost:
      continue
    
    if dp[a] + c >= dp[b]: continue
    dp[b] = dp[a] + c
    if  i == n:
      chk = True
      
if chk:
  print(-1)
else:
  for i in range(2, n+1):
    print(dp[i] if dp[i] < max_cost else -1 )

웜홀 문제랑 비슷하게 접근했다. 차이점은 웜홀에서는 모든 점에 대해서 탐색했지만 이번에는 1번 도시라는 시작점이 정해졌다는 것이다.

그래서 문제의 조건에 따라 max_count를 정의하고 1번 도시는 0으로 나머지 도시는 max_count로 초기화하였다.
그러고나서 벨만포드의 간선 완화를 진행했는데 만약 a라는 도시가 값이 업데이트 되지 않았다면 그러면 1번 도시에서 a로가는 길을 아직 찾지 못한 것으로 판단, 값이 업데이트 되지 않도록 했다.

그렇게 n-1번 반복하고, 마지막 n번째에서 값이 업데이트 되는 곳이 있다면 음의 사이클이 존재하는 것으로 판단하고 chk에 True를 넣어주었다.

마지막으로 chk가 True이면 -1을 출력하고, 아니라면 나머지 도시에 대한 거리를 출력하였다.

---

처음에 미방문 도시에 대한 처리를 하지 않아서 틀렸을 때 GPT한테 물어보니까 GPT는 음의 사이클이 생기는 지점까지 식별하는 코드를 알려주었다.

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

# 버스 정보 (a, b, c) 형식으로 입력
bus = [list(map(int, input().split())) for _ in range(m)]

max_cost = 500 * 6000 * 30000  # 최대 비용 값 설정
dp = [max_cost] * (n + 1)  # 최단 거리 테이블 초기화
dp[1] = 0  # 시작 노드의 최단 거리는 0

# 벨만-포드 알고리즘
chk = False
for i in range(1, n):
    for a, b, c in bus:
        if dp[a] == max_cost:  # a가 방문되지 않았다면 갱신하지 않음
            continue
        if dp[a] + c < dp[b]:
            dp[b] = dp[a] + c

# 음의 사이클 확인
# n번째 반복에서 dp[b]가 갱신되면 그 노드는 음의 사이클에 영향을 받는 노드
for i in range(1, n):
    for a, b, c in bus:
        if dp[a] != max_cost and dp[a] + c < dp[b]:
            # 음의 사이클이 있는 경우 dp[b]를 갱신하고, 영향을 받는 노드를 추적
            dp[b] = -max_cost  # 음의 사이클이 영향을 미치는 노드는 큰 음수 값으로 표시
            chk = True

# 음의 사이클이 있는지 체크 후 결과 출력
if chk:
    print(-1)
else:
    for i in range(2, n + 1):
        print(dp[i] if dp[i] < max_cost else -1)

n-1번까지 반복한 후에, 다시 for문을 실행하면서 음의 사이클을 통해 값이 업데이트 되는 도시들은 -max_count를 입력함으로써 음의 사이클 상에 존재하는 도시들을 식별할 수 있게 하였다.