처음에는 너무 쉬운 문제라고 생각했다.
이전에 이미 음의 사이클의 존재 여부를 판별하는 웜홀이나 타임머신 같은 문제를 많이 풀어봤기에 "왜 이게 골드1이지?" 라고 생각했다. 그리고 N이 50밖에 안되는걸 보고 "왜 이렇게 N이 작지?" 라고 생각했다.
그러나 곧 정답률이 왜 15퍼밖에 안되는지 알 수 있었다.
처음에 벨만포드로 제출한 코드는 다음과 같다.
import sys
input = sys.stdin.readline
INF = 10**9
def BF():
DP = [INF]*N
DP[start] = 0
for n in range(N):
for i in range(N):
for j in range(N):
if graph[i][j] == INF:
continue
if DP[j] > DP[i]+graph[i][j]:
DP[j] = DP[i]+graph[i][j]
if n == N-1:
if DP[end] == INF:
print("gg")
else:
print("Gee")
return
if DP[end] == INF:
print("gg")
else:
print(-DP[end]+money[end])
N,start,end,M = map(int,input().split())
graph = [[INF]*N for i in range(N)]
for i in range(M):
x,y,w = map(int,input().split())
graph[x][y] = w
money = [*map(int,input().split())]
for i in range(N):
for j in range(N):
if graph[i][j] != INF:
graph[i][j] -= money[i]사이클이 있으면 Gee를 출력하고 없으면 gg 혹은 비용을 출력한다.
그러나 바로 틀렸습니다 가 뜨고 말았다.
이유는 전체 도시에서 사이클이 중간에 존재하더라도 그것이 start >> end 사이에 영향을 주지 않는다면 Gee를 출력하면 안되기 때문이었다.
이것을 해결하기 위해서 벨만포드로 다양한 방법을 시도해보았는데 쉽지 않았다.
결국 N이 매우 작다는 점에서 착안하여 플로이드 워셜로 해결하였다.
import sys
input = sys.stdin.readline
INF = sys.maxsize
N,start,end,M = map(int,input().split())
graph = [[INF]*N for i in range(N)]
for i in range(N):
graph[i][i] = 0
data = []
for i in range(M):
data.append([*map(int,input().split())])
money = [*map(int,input().split())]
for i in range(M):
x,y,w = data[i]
graph[x][y] = min(graph[x][y],w-money[y])
for k in range(N):
for i in range(N):
for j in range(N):
if graph[i][k] != INF and graph[k][j] != INF:
if graph[i][j] > graph[i][k]+graph[k][j]:
graph[i][j] = graph[i][k]+graph[k][j]
cycle = False
for i in range(N):
if graph[i][i] < 0:
if graph[start][i] != INF and graph[i][end] != INF:
cycle = True
if cycle:
print("Gee")
else:
if graph[start][end] == INF:
print("gg")
else:
print(money[start]-graph[start][end])
플로이드 워셜에서 음의 사이클을 판별하는 방법은 자기 자신으로 가는 비용이 음수인 node가 존재하는지를 판별하면 된다. 이때 우리는 start에서 end 사이에 cycle이 존재해야하므로, 자기 자신으로 가는 비용이 음수인 node 중 start와 end 사이에 경로가 존재하는 경우 "Gee"를 출력하도록 하였다.
다른 사람들 풀이를 보면 벨만포드 + BFS, 혹은 벨만포드 + 플로이드워셜 이런식으로 푼 사람들이 많은 것 같은데 , 굳이 그렇게 풀 필요 없이 플로이드 워셜만 쓰는게 더 쉽게 풀 수 있다.
최단 경로 찾기의 다양한 알고리즘 중에서 음의 간선이 존재하는 경우에 대해 깊은 이해를 할 수 있도록 해준 좋은 문제였던 것 같다.
오늘의 교훈) 음의 사이클에 대해 정확하게 판단하자