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

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

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

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

아 어렵네요 ㅠㅠ

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

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

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

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

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

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

아 감사합니다 ㅎㅎㅎㅎ