16707번 - American Tour
제가 이 문제를 접근하는 방식은 이렇습니다.
1 -> 2로 가는 최단거리를 구하면서 사용된 정점들을 저장한다.
사용된 정점들과 각 정점들간의 최단거리를 바탕으로 사용한 간선을 찾아서 수정한다.
수정한 간선을 바탕으로 다시 한번 2->N으로 가는 최단거리를 찾는다.
이렇게 진행했는데... 뭔가 잘 못 생각한 부분이 있어서 틀린 거는 확실한데 어느 부분이 틀렸는지 잘 모르겠어서 질문 남깁니다.
쓸데 없이 긴 코드를 봐주셔서 감사합니다.
저랑 같은 방법으로 생각하신 것 같아서 글 남깁니다!
아래의 경우, 2까지 최단으로 갔을 경우에 N까지 가는 길이 없어지는 경우가 발생합니다
3 3 1 2 9 1 3 1 3 2 3
아 감사합니다. 그 경우가 생각이 안났었네요 ㅜ
몇 일 고민했는데 정말 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
forget1026 5년 전
제가 이 문제를 접근하는 방식은 이렇습니다.
1 -> 2로 가는 최단거리를 구하면서 사용된 정점들을 저장한다.
사용된 정점들과 각 정점들간의 최단거리를 바탕으로 사용한 간선을 찾아서 수정한다.
수정한 간선을 바탕으로 다시 한번 2->N으로 가는 최단거리를 찾는다.
이렇게 진행했는데... 뭔가 잘 못 생각한 부분이 있어서 틀린 거는 확실한데 어느 부분이 틀렸는지 잘 모르겠어서 질문 남깁니다.
쓸데 없이 긴 코드를 봐주셔서 감사합니다.