[파이썬] 백준 13907번: 세금

백준 13907번: 세금 13907번: 세금 문제 주언이는 경제학을 배워 행상인이 되었다. 두 도시를 오가며 장사를 하는데, 통행료의 합이 가장 적은 경로로 이동하려 한다.

도시들은 양방향 도로로 연결되어있으며, 도로마다 통행료가 존재한다. 그런데 정부는 세금 인상안을 발표하였다.

세금을 한 번에 올리면 문제가 발생할 수 있으므로 여러 단계에 걸쳐서 올린다고 한다. 세금이 A만큼 오르면 모든 도로의 통행료가 각각 A만큼 오르게 된다.

세금이 오르게 되면 주언이가 내야 하는 통행료가 변할 수 있다. 주언이를 도와 초기의 최소 통행료와 세금이 오를 때마다의 최소 통행료를 구하시오... www.acmicpc.net 접근 방법 (핵심 아이디어) 다익스트라를 이용하여, ' 거쳐간 노드의 수 ' 별로 최단거리를 구해줍니다.

세금은 모든 간선에 동일하게 적용됨 => 최종 비용은 도착지까지 거쳐간 노드의 수에만 종속됨. 거쳐간 노드의 수 별로 최단거리를 구해주면 해결됨.

추가로 "더 적은 노드만 ...