풀이 가중치가 양수인 간선은 양방향, 음수인 간선은 단방향인 그래프에서 출발 정점에서 도착 정점까지 돌아오는 음수사이클이 존재하는지 확인하면 되는 문제다. 특이한 점이라 하면 출발점이 주어지지 않았고, 그래프 내에 어디든 상관없이 조건에 부합하는 음수 사이클이 존재하는지 여부만 알면 되는 문제다. 때문에 모든 정점을 출발점으로 간주하고 bellman ford를 여러 번 진행해야 한다. 만약 탐색 후 dist가 inf가 아니라면, 이미 탐색을 한 번 완료한 그래프이기에, 탐색이 되지 않은 또 다른 그래프에 대해서만 탐색을 진행해주었다. 좀 더 빠르게 탐색해보자. 어떤 정점을 기준으로 조건에 부합하는 음수 사이클이 존재하는지 모르기 때문에, 어차피 모든 정점에 대한 탐색이 이루어져야 하며 매 탐색마다 시작 ..
