728x90
https://www.acmicpc.net/problem/5719
5719번: 거의 최단 경로
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있��
www.acmicpc.net
문제해결
1. 다익스트라 알고리즘을 통해 목적지까지의 최단 거리를 구한다.
2.최단거리를 구하면서 최단거리의 이전노드들을 trace 벡터에 저장하면서 구한다.
3.trace의 있는 노드의 간선들을 재귀를 통해서 제거한다.
4.다시 한번 다익스트라 알고리즘을 돌려서 최단거리를 구한다.
5.코드에 주석 열심히 달았어요 보면은 이해 될 거예요.
코드
ide.goorm.io/shared_files/sksj0111_22aa2b16414dd1737b03c1d57179161b1603205123790
728x90
'그래프 이론 > 다익스트라 알고리즘' 카테고리의 다른 글
| [백준/C++][네트워크 복구(2211번)] (0) | 2020.12.04 |
|---|---|
| [C++알고리즘][다익스트라 알고리즘 개념설명]-최단거리 알고리즘 (0) | 2020.11.29 |
| [백준/C++] K번째 최단경로 찾기(1854번) (0) | 2020.10.23 |