Hello, Freakin world!

www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있�� www.acmicpc.net 먼저 다익스트라 알고리즘으로 최단 거리를 구하면서 최단거리를 갱신할 때 노드의 부모들을 저장해줍니다. 그리고 최단 거리 노드들의 부모들을 순회하면서 간선을 없애고 다시 최단 거리를 구해 반환합니다. 구현 상의 팁 부모 정점들을 저장할 때 최단 거리가 갱신될 경우, 이전의 부모 정점 리스트를 버리고 새로운 리스트를 할당해 저장해야 합니다. 그리고 저장해놓은 최단 거리와 큐에 저장..

www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 다익스트라 알고리즘으로 풀기 전에 DP로 풀 수 있지 않을까? 라고 생각했지만 어렵겠다고 결론을 내렸습니다. 이유는 수빈이가 x-1로도 움직일 수 있기 때문입니다. 점화식은 구해지지만 이 경우 재귀로 풀어야 하는데 시간복잡도가 O(3^n)이 되므로 불가능합니다. 전형적인 다익스트라 알고리즘에 약간 추가로 생각해줘야 할 점이 있습니다. 그래프 노드의 범위를 정해주는 겁니다...

www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어� www.acmicpc.net 이 문제의 핵심은 1의 상황을 2로 바꿔서 풀 수 있다는 걸 이해하는 겁니다. 다익스트라는 단일 시작점을 기준으로 모든 정점 간의 최단 거리를 계산하기 때문에 1번과 경우에 1,2 정점에서 X까지의 최단 거리를 구하려면 1,2 정점 각각에서 최단 거리를 구해야합니다. 이 경우는 비효율적이기 때문에 2번처럼 간선을 역전시켜 1번의 상황을 한번의 다익스트라 알고리즘을 통해서 해결할 ..

www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 주의할 점은 출발지와 도착지가 같지만 가중치가 다른 간선이 주어질 수 있다는 점입니다. 이 점 때문에 인접 행렬이 아니라 인접 리스트로 간선을 표현해야 합니다. ... /* 최소 비용 구하기 https://www.acmicpc.net/problem/1916 */ public class Main { static int n,m; static long INF = Long.MAX_VA..