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 이 문제는 다익스트라를 이용한 최단 경로 문제이다. 이문제의 특성이라면 최단 경로로 갔다가? 다시 돌아와야한다 이러한 점만 고려하면 기본적인 다익스트라 알고리즘에 문제의 조건에만 맞게 해주면 해결 가능하다. import sys import heapq n, m, x = map(int, sys.stdin.readline().split()) graph = [[] for _..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net import sys import heapq n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) INF = int(1e9) distance = [INF] * (n+1) graph = [[] for i in range(n+1)] for _ in range(m): a,b, cost = map(int,sys.stdi..

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 import sys import heapq INF = int(1e9) n, e = map(int, sys.stdin.readline().split()) start = int(sys.stdin.readline()) graph = [[] for i in range(n+1)] distance = [INF] * (n+1) for i in range(e): u, v, ..

최단 경로 최단경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길찾기' 문제라고도 불린다. 최단 경로 알고리즘 유형에는 다양한 종류가 있는데. 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다. 예를 들어 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 등의 다양한 사례가 존재한다. 이런 사례에 맞는 알고리즘을 알고 있다면 문제를 좀 더 쉽게 풀 수 있다. 최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점간 연결된 도로는 그래프에서 '간선'으로 표현된다. 또한 코딩테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출..