다익스트라 연습중 www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 초(시간) 에 해당하는걸 간선의 가중치로, 각각의 점 위치를 노드로 보면 그래프에서의 N번 노드에서 K번 노드까지의 가중치의 최소값을 구해주면 되므로 다익스트라로 해결할 수 있다. 단순한 다익스트라에, 간선조건조차 그리 어려운 편이 아니므로 자세한 설명은 생략해도 괜찮을 것 같다. 더보기 #include #define INF 123456789 using nam..

누가봐도 다익스트라같이 생긴 문제이고, 실제로 다익스트라를 빠삭하게 이해하고 있다면 해결할수 있는 문제였다. www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 다익스트라는 탐색 도중에서 의도적으로 최단경로가 아닌 경우를 배제하는데, 이 배제되는 경로들을 전부 잘 저장해두고 정리해주면 된다. if(ans[next].size() < k){ pq.push({-(dist+dis), next}); ans[next..