lsn1106   4년 전

일반적인 다익스트라에선 체크배열을 만들어서 한 정점 당 한번씩만 큐에서 처리하도록 하는 걸로 알고 있습니다.

하지만 이 문제에선 어떤 정점이 여러번 방문될 수 있으므로 '단, 하나의 도시를 여러번 방문할 수 있다' 조건을 추가해야 하는 것 같습니다.

실제로 해외 저지사이트인 cses에선 다음과 같이 해당 조건을 명시하고 있습니다.

https://cses.fi/problemset/task/1196

"A route can visit the same city several times."
 

startlink   3년 전

수정했습니다.

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