Leta Learns

문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 어제 푼 다익스트라 코드 이용해서 조금만 손 봤더니 그냥 풀렸다.. 다익스트라 코드 외우면 이 문제 저 문제 풀기 수월하겠네. 외워야겠다. 시작점, 도착점만 입력 받아서 다익스트라 이용해서 dist 배열 구하고 변수(cost) 에 저장한 다음, 해당 배열의 도착점 인덱스 값을 출력해주면 된다. (cost[end]) import sys import heapq ..

문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라.. 아무 생각 없이 시도했다가... 피 봤다.... heapq 쓰는 방법 어려워서 고민하다가 다익스트라 예제 코드 구글링해서 참고했다. 이 문제에서 포인트는 파티를 여는 마을(x)로 갈 때 dijkstra 한 번, 파티가 끝나고 집에 갈 때 dijkstra 한 번. 총 두 번 dijkstra 함수를 호출해야 한다는 것이다. dijkstra 함수 내부에..

최단 경로 알고리즘 (Shortest Path) 그래프에는 어떤 정점에서 다른 정점으로의 사이를 잇는 최단 경로를 구하는 알고리즘이 존재한다. ( != MST ) MST : N-1개의 간선으로 최소 가중치 트리 만듦 그래프 내의 모든 간선의 가중치가 0 이상인 경우 => Dijkstra 알고리즘을 이용한다. 그래프가 음수 가중치 간선을 포함하는 경우 => Bellman-Ford 알고리즘을 이용한다. Dijkstra 알고리즘 출발 정점으로부터 가장 가까운 아직 방문하지 않은 정점을 찾고, 다른 모든 정점까지의 거리에 대해서 선택된 정점을 지나서 가는 경우와, 직접 가는 경우 중 최솟값으로 최단 거리를 갱신해가면서 가장 가까운 정점을 하나씩 방문한 정점 집합에 추가하는 방식으로 최단 경로를 갱신. (음의 간..