거의최단경로
-
[백준 BOJ/C++] 5719 거의 최단 경로알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 8. 15. 22:37
5719번: 거의 최단 경로 다익스트라 알고리즘을 통해 최단 경로를 찾아내는 전형적인 문제에서 살짝 꼬아서 난이도를 높인 문제다. 문제 이름에서 유추할 수 있듯 최단 경로를 제외한 그 다음 최단 경로를 찾아 그 길이를 출력해야 한다. 예를 들어 아래 그림과 같은 입력이 주어졌을 때 굵은 화살표로 표시된 최단 경로가 아니라 점선으로 표시된 그 다음 최단 경로를 찾아야 한다. 주어진 예제와 같이 최단 경로는 여러개일 수 있으며 이 경우 모든 최단 경로가 제외되어야 한다. 문제의 포인트 주어진 입력을 어떻게 그래프로 표현할 것인가? 최단 경로를 어떻게 찾고 어떻게 제외시킬 것인가? 그래프의 표현 입력은 다른 일반적인 그래프 문제와 같이 간선의 정보로 주어진다. 각 간선은 단방향이고 길이라는 가중치를 가지고 있..