벨만포드로 1916 최소비용 구하기 풀어보기

벨만포드는 모든 간선에 대해서 정점-1번 돌아야만 최단거리를 구할 수 있게된다

따라서 이 문제의 시간제한이 0.5초이기 때문에 시간초과가 날 것 같지만 실제로 나진 않았다

 

그 이유는 아래 링크에서 찾을 수 있다

https://www.acmicpc.net/board/view/37856

 

간단한 연산은 1억=1초로 계산하지 않고 좀 더 여유를 줘도 상관이 없다

 

문제: https://www.acmicpc.net/problem/1916

소스코드: https://github.com/surinoel/boj/blob/master/1916_bellman.cpp