가득 채우기?

시간 제한1초메모리 제한128 MB

요약

탱크 용량 c, 출발 도시 s, 도착 도시 e가 주어질 때, 각 도시의 연료 가격을 고려해 s에서 e까지 가는 최소 연료 비용을 구하고, 갈 수 없으면 impossible을 출력한다.

난이도: 보통10점 중 7점
유형: 그래프, 최단 경로, 동적 계획법, 힙
정답자: 아직 제출이 없습니다

문제

이번 여름 유럽 자동차 여행의 영수증을 정리하다가, 방문한 도시마다 기름값이 달랐다는 것을 알게 되었습니다. 어디에서 주유할지를 조금 더 영리하게 골랐다면 돈을 아낄 수 있었을지도 모릅니다.

다른 여행자를 돕고(그리고 다음번에는 스스로 돈을 아끼기 위해), 도시 사이를 이동하면서 도중에 주유하여 가장 저렴하게 이동하는 방법을 찾는 프로그램을 작성하려고 합니다. 모든 자동차는 거리 1당 연료 1을 소비하며, 연료 탱크가 빈 상태로 출발한다고 가정합니다.

입력

첫 줄에는 도시의 수 $n$ 과 도로의 수 $m$ 이 주어집니다 ( $1 \le n \le 1000$ , $0 \le m \le 10000$ ).

다음 줄에는 $n$ 개의 정수 $p_i$ 가 주어지며 ( $1 \le p_i \le 100$ ), $p_i$ 는 $i$ 번째 도시의 연료 가격입니다. 도시는 $0$ 번부터 $n-1$ 번까지 번호가 매겨집니다.

이어서 $m$ 개의 줄에 각각 세 정수 $u$ , $v$ , $d$ 가 주어집니다 ( $0 \le u, v < n$ , $1 \le d \le 100$ ). 이는 도시 $u$ 와 $v$ 사이에 길이 $d$ 인 도로가 있음을 뜻합니다.

그다음 줄에는 질의의 수 $q$ 가 주어지고 ( $1 \le q \le 100$ ), 이어서 $q$ 개의 줄에 각각 세 정수 $c$ , $s$ , $e$ 가 주어집니다 ( $1 \le c \le 100$ ). 여기서 $c$ 는 자동차의 연료 탱크 용량, $s$ 는 출발 도시, $e$ 는 목표 도시입니다.

출력

각 질의에 대해, 주어진 용량의 자동차로 도시 $s$ 에서 $e$ 까지 가는 가장 저렴한 여행 비용을 출력합니다. 만약 그 자동차로 $s$ 에서 $e$ 까지 갈 방법이 없다면 impossible을 출력합니다.

예제3

예제 1

입력

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

예제 2

입력

예상 출력

15
impossible
300

예제 3
입력
```
3 0
1 2 3
2
5 0 0
5 0 1
```
예상 출력
```
0
impossible
```