1854번 - K번째 최단경로 찾기
일반적인 다익스트라에선 체크배열을 만들어서 한 정점 당 한번씩만 큐에서 처리하도록 하는 걸로 알고 있습니다.
하지만 이 문제에선 어떤 정점이 여러번 방문될 수 있으므로 '단, 하나의 도시를 여러번 방문할 수 있다' 조건을 추가해야 하는 것 같습니다.
실제로 해외 저지사이트인 cses에선 다음과 같이 해당 조건을 명시하고 있습니다.
https://cses.fi/problemset/task/1196
"A route can visit the same city several times."
수정했습니다.
댓글을 작성하려면 로그인해야 합니다.
lsn1106 4년 전 2
일반적인 다익스트라에선 체크배열을 만들어서 한 정점 당 한번씩만 큐에서 처리하도록 하는 걸로 알고 있습니다.
하지만 이 문제에선 어떤 정점이 여러번 방문될 수 있으므로 '단, 하나의 도시를 여러번 방문할 수 있다' 조건을 추가해야 하는 것 같습니다.
실제로 해외 저지사이트인 cses에선 다음과 같이 해당 조건을 명시하고 있습니다.
https://cses.fi/problemset/task/1196
"A route can visit the same city several times."