개발/알고리즘
[백준 11657] 타임머신 (python)
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 벨만-포드 알고리즘을 사용하자! 처음에 시작점이 정해져있고 각각의 나머지 도시로 가는 최단거리를 구하는 것이기에 다익스트라 알고리즘으로 시도했다. 하지만 음의 순환이 있다면 음의 순환을 통해 무한으로 값을 줄일 수 있으므로 다익스트라 알고리즘을 사용하지 못한다고 한다. 다익스트라와 원리는 비슷하지만 queue에 넣고 최소가중치를 찾는 것이 아니라 모든 정점(N개)에 연결되있는 것들을 N-1번 반복한다. ..
2021. 5. 9. 21:30
최근댓글