1504번 - 특정한 최단 경로
말도 안되는 경로의 거리를 출력하고 있는건 아닐까 의심해보시기 바랍니다
이 문제에서 아래와 같은 두 가지의 경로 말고는 존재할 수 없습니다
/// d() = dijkstra()1)경로 : 1 -> via1 -> via2 -> n거리 : d(1, via1) + d(via) + d(via2, n)2) 경로 : 1 -> via2 -> via1 -> n거리 : d(1, via2) + d(via) + d(via1, n)
이렇게 "경로 -> 거리"로만 생각하면, 다음과 같은 실수를 할 수 있습니다
거리 : min( d(1, via1), d(1, via2) ) + d(via) + min( d(via2, n), d(via1, n) )
뭔가 보기에는 그럴싸하죠? 그런데 "거리 -> 경로"로 뒤집어 생각해보면, 아래와 같은 말도 안되는 경로의 값이 나올 수 있습니다
거리 : d(1, via1) + d(via) + d(via1, n) (min에 의해 충분히 존재 가능)경로 : 1 -> via1 -> n, via1 -> via2 (????)
저도 이렇게 멍청하게 생각해서 틀렸고, 괜히 정답률이 낮은게 아니였네요;
아래 첨부한 코드로 검증이 가능합니다
다익스트라야 뭐 어련히 알아서 잘 짜실거고요
댓글을 작성하려면 로그인해야 합니다.
thinker99 1년 전
말도 안되는 경로의 거리를 출력하고 있는건 아닐까 의심해보시기 바랍니다
이 문제에서 아래와 같은 두 가지의 경로 말고는 존재할 수 없습니다
/// d() = dijkstra()
1)
경로 : 1 -> via1 -> via2 -> n
거리 : d(1, via1) + d(via) + d(via2, n)
2)
경로 : 1 -> via2 -> via1 -> n
거리 : d(1, via2) + d(via) + d(via1, n)
이렇게 "경로 -> 거리"로만 생각하면, 다음과 같은 실수를 할 수 있습니다
거리 : min( d(1, via1), d(1, via2) ) + d(via) + min( d(via2, n), d(via1, n) )
뭔가 보기에는 그럴싸하죠?
그런데 "거리 -> 경로"로 뒤집어 생각해보면, 아래와 같은 말도 안되는 경로의 값이 나올 수 있습니다
거리 : d(1, via1) + d(via) + d(via1, n) (min에 의해 충분히 존재 가능)
경로 : 1 -> via1 -> n, via1 -> via2 (????)
저도 이렇게 멍청하게 생각해서 틀렸고, 괜히 정답률이 낮은게 아니였네요;
아래 첨부한 코드로 검증이 가능합니다
다익스트라야 뭐 어련히 알아서 잘 짜실거고요