13907번: 세금 (acmicpc.net) 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 시간 복잡도: O(N^2logN + NK) 알고리즘: 다익스트라 최적화 예제 힌트를 보고 깨달으셨을 것입니다. 이 문제는 일반적인 최단 거리 알고리즘으로 풀어서는 안 됩니다. 따라서 저희는 이렇게 접근할 수 있습니다: "최단거리가 바뀌는 조건은 무엇일까?" 최단거리가 바뀌는 조건을 한 번 찾아봅시다. 힌트에서 보듯, 세금이 j만큼 인상할 때마다, ..
