BOJ#1219 오민식의 고민 * 문제https://www.acmicpc.net/problem/1219 * 풀이벨만-포드 최단거리 문제입니다. 간선 cost는 음수이고, 각 노드마다 추가로 돈을 벌 수 있습니다.원하는 것은 S(시작점)에서 D(도착점)까지 갈 때 최대로 벌 수 있는 돈의 액수를 구하는 것입니다. 일반적으로 문제에서 간선의 cost가 양수로 주어지는 반면,이 문제에서는 간선 cost가 음수이므로음수 사이클은 문제가 되지 않고 반대로 양수 사이클인 경우가 문제 됩니다. 벨만-포드 알고리즘에 따라 (엣지수(M)만큼 Relaxation)을 N-1번 반복하고N번째에도 Relaxation이 되면 사이클이 존재함을 알 수 있습니다. 그러나 우리는 사이클 유무를 판단하는 것이 목적이 아니라시작점에서 도..