문제 링크 : https://www.acmicpc.net/problem/11657 이 문제는 1번 도시에서 출발해서 각 도시까지의 최단 거리를 출력하는 문제이다. 여기까지만 보면 다익스트라 알고리즘을 이용하면 될 것처럼 보이지만다익스트라 알고리즘을 사용하기 위한 조건중 하나는 무조건 에지가 양수여야 한다는 것이다.하지만 이 문제를 조건을 보면 에지의 값이 음수도 가능하다. 따라서 다익스트라가 아닌벨만 포드 알고리즘을 사용해서 풀어야 한다. 벨만 포드 알고리즘은 시작 정점부터 각각의 정점까지의 최단거리도 구할 수 있지만 음수 사이클이 존재하는지여부도 알 수 있다. 예제 1번을 보면 위와 같이 음수 사이클이 생성되는 것을 알 수 있다. 벨만 포드 알고리즘을 수행하기 위해서 우선 거리배열을 선언하는데 이때 출..