oVeron

https://www.acmicpc.net/problem/1219 1219번: 오민식의 고민 첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착 www.acmicpc.net 문제의 기본적인 토대는 평범한 벨만-포드 알고리즘이다. 이 문제가 G1인 이유는, 사이클이 존재할 때 그대로 Gee를 출력하면 안 된다는 것을 놓치기 쉽기 때문이다. 사이클이 존재하더라도 사이클을 이루는 노드들로부터 도착 지점까지 갈 방법이 없다면, 도착 지점에서 돈을 무한히 가질 수 없다. 따라서 사이클의 노드들로부터 도착 지점까지 갈 수 있는지 확인하는 과정을 반드시 거쳐야 한다. #incl..

알고리즘/baekjoon 2023. 1. 20. 02:53