개발하는 리프터 꽃게맨입니다.

1. 아이디어1) 음의 가중치가 존재하고, 문제 자체가 음의 사이클 또한 염두하고 있기 때문에 해당 문제는 벨만-포드 알고리즘을 사용하는 것이라고 볼 수 있습니다. 2) 즉, 1번 노드에서 출발하여 그래프에 대해서 최단 거리를 갱신한 뒤 문제의 요구에 맞게 출력을 하면 되겠습니다. 3) 음의 사이클을 분별하는 방법은벨만 포드 알고리즘의 결과 dist 배열과벨만 포드 루프를 1번 더 돌린 dist 배열이 다를경우 음의 사이클 이라고 판단할 수 있습니다.2. 주의할 점1) 가중치의 경우의 수가 int 오버플로를 발생시킬 수 있기 떄문에 long long 이나 __int64를 사용해야 합니다.2) 1번 노드에서 그 어떤 노드로 간선이 존재하지 않는 경우에는 그래프에 음의 사이클이 존재하던 말던,-1 을 N-1..

1. 다익스트라 알고리즘의 한계다익스트라 알고리즘은 최단거리를 찾는 일반적인 알고리즘입니다.그러나 그래프 간선의 가중치의 값이 음수일 경우 항상 최적해를 찾는다는 보장은 없습니다. 물론, 다익스트라 알고리즘이 음수 가중치가 존재한다고 해서 항상 최단거리를 찾지 못하는 것은 아닙니다.   먼저, 우선순위 큐를 사용하지 않는 다익스트라 알고리즘 위 그래프에서 최단거리를 찾아낼 수 없습니다.모든 간선의 가중치가 양수일 경우 방문하지 않은 vertex 중 distance 배열의 값이 최소인 노드는 자명하게 최단거리이기 때문이죠. 그러나 음의 가중치 값이 그래프에 존재할 경우미래에 더 저렴한 경로를 찾을 가능성이 존재합니다.  위와 같은 그래프에서는 우선순위 큐를 사용한 다익스트라 알고리즘으로 최단거리를 찾아낼 ..