16952번 - 체스판 여행 2
bfs를 사용해 가중치를 구한 뒤, 1부터 N*N까지의 다익스트라를 사용하려고 접근해봤고,
최단경로가 여러개인 경우가 문제인가 싶어 원래 가중치에 10000을 곱한채로 두고 말을 바꾼 경우에 가중치를 1 추가하는 방식으로 시도해봤는데, wa가 나옵니다.
어느 경우에 문제가 될까요?
다른 방식으로 짜서 ac를 받았고, 랜덤하게 테케만들어서 반례를 찾긴 했습니다. 그런데 어떻게 고칠지는...잘 모르겠네요.
747 23 36 6 17 29 31 21 9 22 46 34 13 35 44 3 38 30 12 7 20 42 43 24 40 1 11 48 33 18 49 16 4 5 45 19 37 32 41 2 15 8 27 28 39 14 26 25 10
ans : 84 3
댓글을 작성하려면 로그인해야 합니다.
bjh3502 1년 전
bfs를 사용해 가중치를 구한 뒤, 1부터 N*N까지의 다익스트라를 사용하려고 접근해봤고,
최단경로가 여러개인 경우가 문제인가 싶어 원래 가중치에 10000을 곱한채로 두고 말을 바꾼 경우에 가중치를 1 추가하는 방식으로 시도해봤는데, wa가 나옵니다.
어느 경우에 문제가 될까요?