목록Bellman-ford Algorithm (1)

dh_0e

[PS] 타임머신, 웜홀 (벨만-포드 기초) / C++ (백준 11675, 1865번)

타임머신 (백준 11675번)웜홀 (백준 1865번)음수 간선을 포함한 그래프의 최단 거리 혹은 음수 사이클을 찾고 싶을 때, 사용하는 벨만-포드 알고리즘에 대해 공부할 수 있었다.그래프에 음수 간선이 포함되어 있으면, 그리디하게 진행되는 다익스트라로는 최단 거리를 구할 수 없음. 플로이드 워셜은 가능은 하지만 $O(V^3)$이고, 벨만-포드는 $O(VE)$ 만에 해결할 수 있음 타임머신(11675)벨만-포드 알고리즘을 구현만 하면 되는 기초 문제.음수 사이클을 돌 때, 최악의 상황에서 -10,000을 500(최대 정점 수) x 6000(최대 간선 수)번 더할 수 있으므로 최대 -30억에 접근할 수 있도록 long long을 설정해줘야 됨#include#include#includeusing namespa..
Problem Solving/Baekjoon 2025. 12. 17. 15:12
이전 Prev 1 Next 다음