[백준 / BOJ] 11657 타임머신 (SPFA)
문제 출처 : 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 N개의 도시가 있다. 1번도시에서 출발하여 모든 도시로 갈때, 최소한의 시간으로 가는 경우를 구한다. 도시간의 시간에는 음수가 존재할수있으며, 이는 타임머신을 타고 과거로 가는경우이다. 만약 과거로 계속해서 갈수있으면 -1 을 출력하고 종료한다. 1번도시에서 해당하는 i번 도시로 갈수없다면 -1을 출력한다. 풀이 벨만포드 풀이 : dlw..
[백준 / BOJ] 11657 타임머신 (벨만포드)
문제 출처 : 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 N개의 도시가 있다. 1번도시에서 출발하여 모든 도시로 갈때, 최소한의 시간으로 가는 경우를 구한다. 도시간의 시간에는 음수가 존재할수있으며, 이는 타임머신을 타고 과거로 가는경우이다. 만약 과거로 계속해서 갈수있으면 -1 을 출력하고 종료한다. 1번도시에서 해당하는 i번 도시로 갈수없다면 -1을 출력한다. 풀이 음수가중치가 존재함으로,..
