통행료 timer 1초 memory 512MB

한 트럭 운송 회사가 내부 프로세스를 최적화하려 한다. 이 최적화는 주로 비용 절감을 의미한다. 회사는 특정 지역을 대상으로 운영하며, 이 지역에서는 모든 도로를 지날 때 통행료를 지불해야 한다. 각 도로는 두 장소(도시, 마을 등)를 직접 연결한다. 회사는 여러 주문을 수행하는데, 각 주문은 한 장소에서 다른 장소로 물품을 운반하도록 지시한다. 회사를 위해 각 주문에 대해 최소 통행료를 계산하려 한다.

지역의 도로 네트워크는 그래프로 모델링할 수 있으며, 각 간선(edge)은 해당 도로의 통행료를 나타낸다. 따라서, 회사는 이 그래프에서 두 노드 간의 최소 비용 경로를 찾으려 한다.

그래프에는 특별한 성질이 있다:

• 그래프는 방향성(directed)을 가지며,

• 특정 상수 K에 대해 ⌊b/K⌋ = 1 + ⌊a/K⌋가 만족되는 경우에만 a에서 b로의 간선이 존재한다.

당신은 각 주문에 대해 최소 통행료를 계산하는 프로그램을 작성해야 한다.