有?NN?个城市（编号?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，分别表示车子油箱容量?C、起点城市 S、终点城市?E。
输出格式
对于每个问题，输出一个整数，表示所需的最少油钱。
如果无法从起点城市开到终点城市，则输出?impossible。
每个结果占一行。
数据范围
1≤N≤1000
1≤M≤10000,
1≤pi≤100,
1≤d≤100,
1≤C≤100
输入样例：
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?分析：
这里需要注意的是状态的转移，除了一个点可以转移到与它相连的下一点，还可以一个点转移到加一单位油的状态，dp[i]存的是当前所花费的钱数，我的dp只用了一维，因此我的i%n表示地点的id，i/n表示的是当前油量，其实可以设置成一个二维数组，这样可能写起来更方便。
代码如下：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N=1e5+1e3+10;
const int INF=0x3f3f3f3f;
struct node{
int v,w;
friend bool operator < (node a,node b)
{
return a.w>b.w;
}
};
int p[N],dp[N];
bool st[N];
vector<node>adj[1010];
int n,m;
int c,s,e;
int dij()
{
priority_queue<node>q;
q.push({s,0});
dp[s]=0;
while(q.size())
{
node u=q.top();
q.pop();
if(st[u.v]) continue;
if(u.v==e) return u.w;
st[u.v]=true;
int u1=u.v%n,d1=u.v/n;
if(d1<c&&dp[u.v+n]>dp[u.v]+p[u1])
{
//cout<<u.v<<" "<<dp[u.v]+p[u1]<<endl;
dp[u.v+n]=dp[u.v]+p[u1];
q.push({u.v+n,dp[u.v+n]});
}
for(int i=0;i<adj[u1].size();i++)
{
int v=adj[u1][i].v,w=adj[u1][i].w;
if(d1<w)continue;
if(dp[v+(d1-w)*n]>dp[u.v])
{
dp[v+(d1-w)*n]=dp[u.v];
q.push({v+(d1-w)*n,dp[u.v]});
}
}
}
return -1;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)cin>>p[i];
while(m--)
{
int u,v,d;
cin>>u>>v>>d;
adj[u].push_back({v,d});
adj[v].push_back({u,d});
}
int q;
cin>>q;
while(q--)
{
cin>>c>>s>>e;
fill(dp,dp+N,INF);
fill(st,st+N,false);
int d=dij();
if(d==-1)cout<<"impossible"<<endl;
else cout<<d<<endl;
}
return 0;
}
