다익스트라

[Gold IV] 플로이드 - 11404문제 링크분류플로이드–워셜, 그래프 이론, 최단 경로문제 설명n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 ..

[Gold III] 파티 - 1238문제 링크분류데이크스트라, 그래프 이론, 최단 경로문제 설명N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.입력첫째 줄에 N(1 ≤ N ≤ 1,..

다익스트라 알고리즘이란?다익스트라 알고리즘(Dijkstra's Algorithm)은 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger Dijkstra)가 고안한 알고리즘으로, 그래프에서 한 노드(정점)에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 가중치가 있는 그래프에서 사용되며, 특히 가중치가 음수가 아닌 경우에 유효하다.동작 원리1. 시작 노드 설정시작 노드를 설정하고, 시작 노드에서 다른 모든 노드로의 거리를 무한대로 설정한다. 시작 노드의 거리는 0으로 설정한다.2. 미방문 노드 집합 설정모든 노드를 미방문 노드 집합에 넣는다.3. 최단 거리 노드 선택처음에는 시작노드가 선택되고, 이후에는 미방문 노드 중에서 현재 가장 짧은 거리를 가진 노드를 선택한다.4. 거리..

[Gold V] 최소비용 구하기 - 1916문제 링크성능 요약메모리: 56844 KB, 시간: 512 ms분류데이크스트라, 그래프 이론, 최단 경로제출 일자2024년 11월 19일 03:29:38문제 설명N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.입력첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 ..

[Gold IV] 최단경로 - 1753문제 링크성능 요약메모리: 124632 KB, 시간: 768 ms분류데이크스트라, 그래프 이론, 최단 경로제출 일자2024년 11월 19일 02:54:46문제 설명방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.입력첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 ..