도시간 이동 비용 (벨만 포드 응용)

문제 설명 N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때 한 도시에서 다른 도시로 이동하는데 쓰이는 비용의 최소값을 구하는 프로그램을 작성하세요. 첫 줄에 도시의 수N(N<=100)과 도로수 M(M<=200)가 주어지고, M줄에 걸쳐 도로정보와 비용이 주어진다.

만약 1번 도시와 2번도시가 연결되고 그 비용이 13이면 “1 2 13”으로 주어진다. 그 다음 마지막 줄에 출발도시와 도착도시가 주어진다.

입력예제 5 7 1 2 5 1 3 4 2 3 -3 2 5 13 3 4 5 4 2 3 4 5 7 1 5 출력예제 14 소스 코드 아래 영상을 참고하여 구현해보았다. #include #include using namespace std; struct Edge { int from; int to; int dis; }; vector map; vector dist; int n, m; //Relax는...