728x90 116571 [C++] 백준 11657번: 타임머신 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 중요풀이 벨만-포드 알고리즘을 사용하는 대표적인 예제 문제입니다. 노드 사이에 가중치가 음수값을 갖기 때문에 다익스트라 알고리즘이 아닌 벨만-포드 알고리즘을 사용해줍니다. 거리 값이 INF이 아닌 노드들을 체크하여 이동할 수 있는 간선의 가중치를 계산하여 더 작은 값으로 갱신해 줍니다. 여기서 음의 가중치를 갖는 간선이 있다면 그 구간을.. 2021. 8. 27. 이전 1 다음 728x90
