randoms   3년 전

다른분들이 푼 방법과 마찬가지로

min(1-a-b-n , 1-b-a-n)

을 출력해서 맞았습니다.


그런데 문제를 잘 보면 같은 정점을 다시 방문 할 수 있으니까

1-a-1-b-n, 1-b-1-a-n, 1-a-n-b-n, 1-b-n-a-b 도 고려해야할 대상이 되지 않을까요??


이게 아니라면 문제 취지상

출발점(1)과 도착점(N)은 한번만 방문한다. 

라는 문구를 추가해주셨으면 좋겠습니다

ntopia   3년 전

모든 거리가 양수이므로 위에 제시하신 경로들은 모두 답이 될 수 없음을 증명할 수 있습니다

ntopia   3년 전

적어도 min(1-a-b-n , 1-b-a-n) 보다는 같거나 크다고 말하는게 정확하겠네요

randoms   3년 전

1 - 2 : 1

1 - 3 : 1

2 - 3 : 9

2 - 4 : 9

3 - 4 : 1

이면 1-2-1-3-4 : 4가 최소가 돼요

ho94949   3년 전

1-2-3-4로 가는것도 4입니다. 왜냐하면 2부터 3까지의 최단경로는 9가 아닌 1-2와 1-3을 이용한 2이거든요.

randoms   3년 전

아하 그렇네요! 감사합니다~

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