forget1026   5년 전

제가 이 문제를 접근하는 방식은 이렇습니다.

1 -> 2로 가는 최단거리를 구하면서 사용된 정점들을 저장한다.

사용된 정점들과 각 정점들간의 최단거리를 바탕으로 사용한 간선을 찾아서 수정한다.

수정한 간선을 바탕으로 다시 한번 2->N으로 가는 최단거리를 찾는다.

이렇게 진행했는데... 뭔가 잘 못 생각한 부분이 있어서 틀린 거는 확실한데 어느 부분이 틀렸는지 잘 모르겠어서 질문 남깁니다.

쓸데 없이 긴 코드를 봐주셔서 감사합니다.

jkd4242   5년 전

저랑 같은 방법으로 생각하신 것 같아서 글 남깁니다!

아래의 경우, 2까지 최단으로 갔을 경우에 N까지 가는 길이 없어지는 경우가 발생합니다 

3 3
1 2 9
1 3 1
3 2 3

forget1026   5년 전

아 감사합니다. 그 경우가 생각이 안났었네요 ㅜ

몇 일 고민했는데 정말 감사합니다.

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