반응형
특정한 최단 경로
-
BOJ) 특정한 최단 경로 (1504 번)알고리즘/백준 2021. 1. 29. 17:14
특정한 최단 경로 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라를 사용한다는 조건에 노드 두 개를 거쳐야하는 경로에 포함해야하는 문제다. 처음에는, 기본적인 다익스트라로 경로를 이동하면서 입력받은 두 노드를 거쳤는지 정보도 함께 포함했었다. 하지만, 틀린 것을 확인하고 두 경로 모두 거쳐야하는 조건을 제대로 파악하기 어렵다고 생각했다.그래서 경로가 두개만 주어지기 때문에, 해당 경로를 거치는 경우의 수를 다익스트라로 표현하면 된다고 생각했다. 풀이 1번..