타임머신 11657 썸네일형 리스트형 [Python][백준 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 풀이 과정 그래프 문제에서 노드간에 걸리는 시간이 음수가 포함했다? -> 벨만 포드 음수 간선에 관하여 최단 경로 문제는 다음과 같이 분류할 수 있다. 1. 모든 간선이 양수인 경우 2. 음수 간선이 있는 경우 2-1) 음수 간선 순환은 없는 경우 2-2) 음수 간선 순환이 있는 경우 벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용할 수 있다. 또한 음수 간선의 감지할 수 있으며, 벨.. 더보기 이전 1 다음
