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

백준 1753 최단경로

문제 : https://www.acmicpc.net/problem/1753 서론 다익스트라 방법으로 풀이했으나 시간초과. 이후 우선순위 큐를 이용한 다익스트라로 해결. 아이디어 다익스트라 알고리즘은 1 -> 2 -> 3-> 4 그래프에서 1번에서 4번까지의 최단경로는 1번에서 2번, 2번에서 3번, 3번에서 4번까지의 최단경로를 포함한다는것을 전제로한다. 즉 최단경로 + 최단경로 = 최단경로다. 정점을 이동할때마다 최단경로를 계속 누적시켜주면 된다. 여기에 우선순위큐를 이용하게 되면 경로 중 최단경로를 우선적으로 탐색하여 탐색횟수를 줄일 수 있다. 구현 우선순위 큐를 이용한 성공한 구현 // c++ #pragma warning (disable : 4996) #include #include #include..

2019. 6. 27. 17:17