Full Tank?

프로그램 명: ncpc_tank

제한시간: 1 초

이번 여름 자동차 여행을 마치고 당신은 자동차의 기름값이 방문한 도시마다 달랐다는 것을 영수증을 통해 알게 되었습니다.아마도 당신은 어디에서 기름을 채우느냐에 따라 돈을 절약할 수 있었을 것입니다.

다른 여행자들을 돕기 위해서(또는 당신이 다음에 돈을 절약하기 위해서) 당신은 두 도시를 여행할때 길가에서 기름을 채울 수 있는 가장 적은 비용이 드는 길을 찾는 프로그램을 만들려고 합니다. 모든 차는 하나의 기름종류를 사용한다고 가정하고, 빈 기름통을 가지고 시작합니다.

입력

첫번째 라인에는 도시의 수 n과 도로의 수 m를 입력합니다.(n = 0 ~ 1000, m = 0 ~ 10000 )
다음 라인에는 p(i), i번째 도시의 기름값을 입력합니다. (1<=p(i)<=100)
그리고 다음 m번의 라인3개의 정수 u, v 그리고 d는 u와 v사이에 도로의 길이 d를 의미합니다. (0<=u, v 다음 라인 q 는 여행하는 차의 대수,(1<=q<=100)
다음 라인 c, s, e (1<=c=<100, s,e<=n)는 각각의 차 마다의 차의 기름탱크 용량 c, 시작하는 도시 s, 그리고 도착하는 도시의 번호 e를 의미합니다.

출력

s에서 시작하여 e에 도착하는 최소 비용을 각각의 차마다 구하시오.

만약 s(출발점)에서 e(도착점)으로 해당 차로 갈 수 없을 때 impossible을 출력합니다.

입출력 예

입력 

5 5  (5개의 도시, 5개의 도로 수) 
10 10 20 12 13  (각 도시마다의 기름값) 
0 1 9 (0번도시와 1번 도시의 도로길이 9)   
0 2 8 
1 2 1 
1 3 11 
2 3 7 
2 (2대의 차가) 
10 0 3 (첫번째 차는 10의 기름용량, 0번 도시에서 시작, 3번 도시에 도착) 
20 1 4 (두번째 차는 10의 기름용량, 1번 도시에서 시작, 4번 도시에 도착) 

출력 

170 
impossible

After going through the receipts from your car trip through Europe this summer, you realised that the gas prices varied between the cities you visited. Maybe you could have saved some money if you were a bit more clever about where you filled your fuel?

To help other tourists (and save money yourself next time), you want to write a program for finding the cheapest way to travel between cities, filling your tank on the way. We assume that all cars use one unit of fuel per unit of distance, and start with an empty gas tank.

입력

The first line of input gives 1 <= n <= 1000 and 0 <= m <= 10000, the number of cities and roads. Then follows a line with n integers 1 <=<= pi <=<= 100, where pi is the fuel price in the ith city. Then follow m lines with three integers 0 <= u, v < n and 1 <= d <= 100, telling that there is a road between u and v with length d. Then comes a line with the number 1 <= q <= 100, giving the number of queries, and q lines with three integers 1 <= c <= 100, s and e, where c is the fuel capacity of the vehicle, s is the starting city, and e is the goal.

출력

For each query, output the price of the cheapest trip from s to e using a car with the given capacity, or “impossible” if there is no way of getting from s to e with the given car.

입출력 예

입력

5 5
10 10 20 12 13
0 1 9
0 2 8
1 2 1
1 3 11
2 3 7
2
10 0 3
20 1 4

출력

170
impossible

출처:ncpc/2007/Problem F
번역: kdkim89

[질/답] [제출 현황] [푼 후(0)]

[ 채 점 ] [홈으로] [뒤 로]