벨만포드알고리즘

https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 주어 www.acmicpc.net 1. Logic 1. 최적경로 즉 시작부터 목적지까지 최단거리로 가는 경우가 있는지를 먼저 파악하기 위해 BFS통해 최단거리를 확인해놓는다. 2. 벨만포드를 돌면서 최단경로를 확인하고 v번을 돌면서 마지막 사이클에서 음의 사이클을 확인한다. 3. 벨만 포드 알고리즘을 돌면서 최단경로를 갱신할 때에만 주의 해야 할 사항 음의 사이클이 있다고 무조건 -1을 반환하는게 아니..