알고리즘/문제풀이 - 백준

백준 1504 특정한 최단 경로

문제 : https://www.acmicpc.net/problem/1504 서론 우선순위 큐를 이용한 다익스트라 알고리즘으로 풀이했다. 아이디어 다익스트라 알고리즘은 1 -> 2 -> 3-> 4가 최단경로일때 1에서 4까지의 최단경로는 1~2까지의 최단경로를 포함하고 2~3까지의 최단경로를 포함한다. 즉 목적지까지의 최단경로는 중간지점들의 최단경로 합이다. 두개의 정점이 n1, n2일때 시작정점부터 두개의 정점을 거쳐서 종료정점까지 가는 방법은 1. 시작정점 -> n1 -> n2 -> 종료정점 2. 시작정점 -> n2 -> n1 -> 종료정점 두개의 방법이 있다. 1번 방법은 시작정점 -> n1의 최단경로, n1 -> n2의 최단경로, n2 -> 종료정점의 최단경로의 합을 구하면 되고 2번 방법도 마찬가..

2019. 6. 27. 20:01