다익스트라2 BOJ 11779 - 최소비용 구하기 2 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 접근 방법 1753 최단경로 문제에 경로까지 출력하는 짬뽕된 문제이다. 다익스트라를 이용하여 문제를 풀어보도록 하자. 기존 priority_queue를 이용한 코드에 경로를 저장하는 것이 이 문제의 핵심이다. 경로를 어떻게 지정할까 생각을 하다 최소신장트리에서 부모를 저장하는 방법을 사용해보기로 했다. 1. 부모를 저장할 parent[] 를 선언 (자기 자신으로 초.. 2024. 2. 21. BOJ 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 접근 방법 최단 경로를 구하는 알고리즘 중, 학부 수업에서 배운 다익스트라를 사용하기로 했다. 다익스트라에 대한 내용은 추후 따로 포스팅을 해야겠다. 간단하게 원리는 다음과 같다. 1. 모든 정점에 최단경로 d를 저장한다. (초기화는 무한으로) 2. priority_queue에 최단 경로 d를 기준으로 오름차순이 되게 한다. 3. pq에서 뽑은 정점을 가지고,.. 2024. 2. 20. 이전 1 다음
