벨만포드

[BOJ] 11657 타임머신

2023.09.08

✨ 최단경로 알고리즘 ➡️ 벨만 포드 알고리즘 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 📍 고려해야할 점 C < 0 인 경우 타임머신으로 시간을 되돌아가는 경우이다. ➔ 음의 가중치 존재 1번 도시에서 출발한다. 음의 사이클이 있거나 경로가 아예 없다면 -1 출력 오버플로우 범위 조심 🕹️ 풀이과정 1️⃣ 간선과 정점, 비용의 정보를 저장한다. 2️⃣ 벨만 포드 알고리즘을 사용..

알고리즘/BOJ

[BOJ] 1865 웜홀

2023.09.08

✨ 최단경로 알고리즘 ➡️ 벨만 포드 알고리즘 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 📍 고려해야할 점 한 지점에서 출발하여 다시 출발했던 지점으로 돌아왔을 때 처음 출발했을 때보다 시간이 되돌아가 있는 경우 판단 ➔ 웜홀 내에서 시간이 거꾸로 흘러간다. ➡️ 음수 가중치 존재 & 음의 사이클 존재 O 한 지점에서 출발한다. (특정 지점에서 출발 X) 임의의 정점에서 출발 모든 정점에서 출발 두 지점을 연결하는 도로가 한 ..

[BOJ] 11657 타임머신

[BOJ] 1865 웜홀

티스토리툴바