본문 바로가기

Algorithm/Bellman-Ford

(2)
(C++) - 백준(BOJ) 11657번 : 타임머신 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 벨만포드 문제였습니다. 풀이방법 1. 매번 edge에대해 벨만포드 알고리즘을 수행합니다. 2. 최단경로는 최대 N개의 정점 N-1개의 간선을 가지므로 N번째 수행시 갱신값이 있다면 음수 사이클 판정을 할 수 있습니다. 3. 음수 사이클이 존재한다면 -1만 출력. 아닐 경우에는 1에서 출발해 2 ~ N으로 가는 정점까지의 시간을 출력. 만..
(C++) - 백준(BOJ) 1865번 : 웜홀 www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 벨만포드 문제였습니다. 풀이방법 모든 정점을 확인하면서 갱신이 되었다면 flag를 세워주고 갱신이 되지 않았다면 다시 돌아올 수 없는 경우므로 flag를 내려주는 방식으로 벨만포드 알고리즘으로 순회하며 정답을 찾습니다. Code #include #define INF 0x3f3f3f3f using namespace std; using pii = pair; int tc; int n, m, w; vect..