inseonyun
commented
2 years ago 문제 요구사항
- V개의 마을과 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다.
- 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다.
- 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.
- 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하라.
- 첫째 줄에 V와 E가 빈칸을 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1))
- 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다.
- a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의미이다.
- (a → b임에 주의) 거리는 10,000 이하의 자연수이다. (a, b) 쌍이 같은 도로가 여러 번 주어지지 않는다.
접근 방법
- 3개의 반복문을 중첩하여, 각각의 반복 인자를 거쳐가는 정점, 출발 정점, 도착 정점으로 사용하여 탐색한다.
풀이 순서
- V와 E 값을 입력 받는다
- 전역 변수로 선언해둔 map[402][402]를 V 크기만큼 INF(987654321) 값으로 초기화 한다.
- E의 크기만큼 반복하여, a(출발 정점), b(도착 정점), c(가중치) 값을 입력 받아 map[a][b] = c로 값을 저장한다.
- 3개의 반복문을 사용한다.
- k는 거쳐가는 정점을 의미 한다.
- i는 출발 정점을 의미 한다.
- j는 도착 정점을 의미 한다.
- map[i][j] ( i 출발 j 도착) 값이 map[i][k] + map[k][j] (i출발 k를 거쳐 j로 도착) 값보다 크면 map [i][j]값을 갱신해준다.
- V 크기만큼 반복하여 map[i][i](i에서 출발하여 i에 도착)값이 result(초기값 INF)보다 작으면 result 값을 갱신 해준다.
- result 값 출력, 만약 result 값이 INF라면 -1 출력
Source URL : https://www.acmicpc.net/problem/1956