날마다 새로운 코딩

1. 문제 : https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 2. 풀이 : Bellman-Ford 3. 설명 '한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우'는 문제에서 주어진 그래프에 음수 싸이클이 존재하는 경우이다. 문제에서 출발 지점을 명시해 주지 않았기 때문에 출발 지점으로 임의의 지점을 선택하여 Bellman-Ford를 수행한 ..

Algorithm/Bellman-Ford 2021. 8. 3. 23:50

1. 문제 : 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 2. 풀이 : Bellman-Ford 3. 시간복잡도 : O(VE) 4. 설명 Bellman-Ford 알고리즘은 'V-1'회의 edge relaxation 수행으로 한 노드로부터 다른 노드까지의 최단 경로를 구할 수 있다. 그림[1]에서 1번 도시로부터 다른 모든 도시까지의 최단 경로를 구해보자. edge relaxatio..

Algorithm/Bellman-Ford 2021. 7. 29. 22:20