nokia   3년 전

dfs로 풀었더니 시간 초과가 나길래 동적계획법을 적용해서 다음 코드를 제출했더니 틀렸다고 나오는데

왜 틀렸는지를 모르겠습니다.




Green55   3년 전

부분문제간의 사이클이 존재할 경우 dp를 사용할 수 없습니다. 이 문제는 다익스트라같은 최단경로 알고리즘을 사용해야 합니다.

nokia   3년 전

혹시 부분문제간의 사이클이 존재한다는게 어떤것을 뜻하는지 알 수 있을까요?

Green55   3년 전

x번 정점의 최단거리를 구하기 위해 y번 정점의 최단거리를 이용하는데,

y번 정점의 최단거리를 구하기 위해 x번 정점의 최단거리를 이용합니다.

댓글을 작성하려면 로그인해야 합니다.