구름

문제 보러가기 : https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 이번 문제는 다익스트라(Dijkstra) 문제였습니다. 최단 경로뿐만 아니라 최단 경로에 포함된 정점들까지 출력해야 하는 문제였습니다. 《문제 풀이》 1. 입력한 출발 도시에서 도착 도시까지의 경로는 단방향이므로 단방향 연결 2. 다익스트라 (최단 경로 구하기) (1) 출발 도시를 큐에 삽입 (2) 출발 도시를 제외한 모든 도시의 거리는 INF (..

문제 보러가기 : www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 이번 문제는 다익스트라(Dijkstra) 문제였습니다. 다익스트라 기본 문제에서 각 지역의 아이템 개수를 담을 배열만 추가해주면 됩니다. 😊 《문제 풀이》 1. 길은 양방향 통행이 가능하므로 두 지역을 양방향으로 연결 2. n개의 지역 중 습득 가능한 아이템의 최대 개수를 구해야 하므로 다익스트라 n번 수행 3. 낙하 지역을 제외한 모든 지역의 거리는 무한대로 초기화 (낙하 지역은 0) 4. 현재까..