문제 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 풀이 solved.ac 난이도: Gold 4 단일 시작점 최단경로 알고리즘의 대표 격인 다익스트라는 음수 가중치의 간선이 있는 그래프에서는 정확한 값을 구할 수 없다. 그 이유는 음수 사이클이 반복된다면 우선순위 큐에 음의 최단 거리를 가지는 정점이 무한히 업데이트되며 삽입될 것이다. 따라서 이번 문제와 같이 간선의 가중치로 음수가 주어지는 경우..