문제 https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 설명 i번 도시에서 i번 도시로 가는 최단경로는 0이지만, 일반적인 k번째 최단경로는 0이 아닐 수 있음에 유의한다. 또, k번째 최단경로가 존재하지 않으면 -1을 출력한다. 최단경로에 같은 정점이 여러 번 포함되어도 된다. 도로의 정보를 저장하기 위한 Road 클래스를 만들고 리스트를 만들어 연결관계를 저장한다. 이때, 소요 시간이 ..
문제 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 설명 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구해야 한다. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력된 간선 정보를 저장할 Edge 클래스를 만들고 리스트를 만들어 연결관계를 저장한다. 시작 정점에서부터 인덱스에 해당하는 정점까지의 최단 거리를 나타내는 minLength[] 배열을 만든다. 음의 가중치가 없는 그래프에서 최단 경..
최단 경로의 종류 단일 출발 최단 경로 어떤 하나의 정점에서 출발하여 나머지 모든 정점까지의 최단 경로를 찾는 문제 음이 아닌 가중 그래프 : 다익스트라 알고리즘 / 모든 가중 그래프 : 벨만-포드 알고리즘 단일 도착 최단 경로 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제 음이 아닌 가중 그래프 : 다익스트라 알고리즘 / 모든 가중 그래프 : 벨만-포드 알고리즘 단일 쌍 최단 경로 어떤 정점 v에서 w로 가는 최단 경로를 찾는 문제 음이 아닌 가중 그래프 : 다익스트라 알고리즘 / 모든 가중 그래프 : 벨만-포드 알고리즘 전체 쌍 최단 경로 모든 정점 쌍들 사이의 최단 경로를 찾는 문제 (플로이드-워셜 알고리즘) 다익스트라 알고리즘 음의 가중치를 갖지 않는 그래프에서 어떤 한 정..
