2697. [POJ 3635]Full Tank?

【题目描述】

有N个城市（编号0、1…N-1）和M条道路，构成一张无向图。

在每个城市里边都有一个加油站，不同的加油站的单位油价不一样。

现在你需要回答不超过100个问题，在每个问题中，请计算出一架油箱容量为C的车子，从起点城市S开到终点城市E至少要花多少油钱？

【输入格式】

第一行包含两个整数N和M。

第二行包含N个整数，代表N个城市的单位油价，第i个数即为第i个城市的油价pi。

接下来M行，每行包括三个整数u,v,d，表示城市u与城市v之间存在道路，且车子从u到v需要消耗的油量为d。

接下来一行包含一个整数q，代表问题数量。

接下来q行，每行包含三个整数C、S、E，分别表示车子油箱容量、起点城市S、终点城市E。

【输出格式】

对于每个问题，输出一个整数，表示所需的最少油钱。

如果无法从起点城市开到终点城市，则输出”impossible”。

每个结果占一行。

【样例输入】

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

【数据范围】

1≤N≤1000,1≤M≤10000,1≤pi≤100,1≤d≤100,1≤C≤100。