백준 1219번 '오민식의 고민' 파이썬(Python) /벨만 포드, bfs or dfs

https://www.acmicpc.net/problem/1219 1219번: 오민식의 고민 문제 오민식은 세일즈맨이다. 오민식의 회사 사장님은 오민식에게 물건을 최대한 많이 팔아서 최대 이윤을 남기라고 했다.

오민식은 고민에 빠졌다. 어떻게 하면 최대 이윤을 낼 수 있을까?

이 나라에는 N개의 도시가 있다. 도시는 0번부터 N-1번까지 번호 매겨져 있다.

오민식의 여행은 A도시에서 시작해서 B도시에서 끝난다. 오민식이 이용할 수 있는 교통수단은 여러 가지가 있다.

오민식은 모든 교통수단의 출발 도시와 도착 도시를 알고 있고, 비용도 알고 있다. 게다가, 오민식은 각각의 도시를 방문할 때마다 벌 수 있는 돈을 알고있다.

이... www.acmicpc.net 난이도 : 플레5 벨만 포드에 bfs 또는 dfs를 사용하는 문제이다. bfs/dfs는 사이클이 발생했을 때, end에도 영향을 주는 지 알아보기 위함이다. 이전 벨만포드 문제들에선 end 상관없이 사이클이 발생하는지를 묻는 문제...