dfwdf77   1년 전

우선순위 큐 다익스트라를 사용해 통행료를 인상할떄마다 간선의 값을 변경시키는데

여기서 시간초과가 나는것 같네요...

이거 어떤 방식으로 풀어야 되죠???

dlwodnsdl   1년 전

통행료 인상할 때마다 다익스트라를 돌리시면 K의 최댓값이 3만이므로 시간초과를 피할 수 없습니다.

힌트를 드리자면 세금을 올릴때마다 어떠한 경로의 통행료의 증가량=지나간 길의 수*세금의 인상분이 되는 거를 이용하시면 됩니다.


dfwdf77   1년 전

그러면 통행료가 증가하면 경로도 바뀌지 않나요?


앞에 힌트처럼 경로 두개를 걸쳐서 가기 때문에 통행료가 인상하면 경로자체가 바뀌지 않나요?

dlwodnsdl   1년 전

S에서 D로 가는 경로중에 어떠한 경로들이 세금이 올랐을 때 최소 통행료 경로가 되는 지를 고려해보시면, 처음에 다익스트라에서 세금이 0일때의 최소경로 뿐만 아니라 어떠한 경로들을 추가적으로 구해야하는지 나옵니다.

dfwdf77   1년 전

아 어렵네요 ㅠㅠ

소스를 어떤식으로 주어야 할지 막막하네요 ㅠㅠ

yohan5050   1년 전

저는 다익스트라를 이용할 때, "dist[n] : n번 도시까지 가는 데 드는 최소 통행료  " 였다면

"dist[n][x] : n번 도시까지 x개의 길을 거쳐서 가는 데 드는 최소 통행료" 로 몇 개의 길을 거쳤는지도 고려해서 풀었어요

그리고 위에서 답변해주신 dlwodnsdl님의 말씀대로 증가량이 지나간 길의 수*세금의 인상분 을 이용하시면 됩니다.

이렇게만 해도 풀리긴 하지만 위에서 답변해주신 것 중에 "세금이 올랐을 때, 어떠한 경로들이 최소 통행료가 되는 지를 고려"하는 부분을 제가 제대로 이해한 건지는 모르겠지만 저는 시간을 줄이는 데 도움이 됐습니다.


그리고 이 문제는 문제 출제하신 분이 게시판에 풀이 올리셨으니 고민하시다가 참고하세요.

dfwdf77   1년 전

아 감사합니다 ㅎㅎㅎㅎ

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