알고리즘/다익스트라3 다익스트라 - k번째 최단 경로 찾기 백준 - 1854: k번째 최단 경로 찾기 https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 $n$, $m$, $k$가 주어진다. ($1 ≤ n ≤ 1\,000$, $0 ≤ m ≤ 2\,000\,000$, $1 ≤ k ≤ 100$) $n$과 $m$은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이 www.acmicpc.net 기존: 우선순위 큐를 이용해서 최단 경로를 선택해 각 노드마다 가질 수 있는 경로를 차례대로 저장하도록 구성, 하지만 모든 노드에 대해서 경로를 저장하는 코드를 구성할 때 저장된 경로가 k개가 안 될 때만 고려함(단순 경로 추가 코드) 피드백: 최단 경로만 찾는 것이 아니기 때.. 2023. 7. 15. 다익스트라 - 최소 비용 구하기 백준 - 1916: 최소 비용 구하기 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 이전 글의 최단 경로 구하는 방식과 동일하게 우선순위 큐를 통해 최단 경로를 비교해 업데이트하고 최종 정답 배열에 저장하는 방식으로 구현하면 된다. #include #include #include #include using namespace std; typedef pair p; vector visited; vector answ.. 2023. 7. 15. 다익스트라 - 최단 경로 구하기 백준 - 1753: 최단 경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 기존: 큐를 이용해서 최단 경로를 업데이트하는 방식을 이용하려 함 --> 구현이 어려웠음 피드백: 우선순위 큐를 이용해 최단 경로를 업데이트하고 저장하는 방식으로 구현 → 기존 슈도 코드 구현이 부실해서 피드백 후의 슈도 코드로 올림 #include #include #include #include using namespace st.. 2023. 7. 15. 이전 1 다음
