Full Tank?

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

//250MS	4900K
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define M 1007
using namespace std;
int n,m,cap,s,e,num;
int val[M],dp[M][M],head[M];
struct node
{
    int u,cost,res;//u代表节点，cost代表当前节点的花费，res代表此节点剩余的油
    bool operator < (const node a)const
    {
        return cost>a.cost;
    }
};
struct E
{
    int v,to,dist;
} edg[M*20];
vector<int>G[M];
void addedge(int u,int v,int dist)
{
    edg[num].v=v;
    edg[num].dist=dist;
    edg[num].to=head[u];
    head[u]=num++;
}
void init()
{
    num=0;
    memset(head,-1,sizeof(head));
    memset(val,0,sizeof(val));
    for(int i=0; i<n; i++)
        G[i].clear();
}
void bfs()
{
    for(int i=0; i<n; i++)
        for(int j=0; j<=cap; j++)
            dp[i][j]=0;
    priority_queue<node> q;
    q.push((node){s,0,0});
    while(!q.empty())
    {
        node x=q.top();
        q.pop();
        int u=x.u,cost=x.cost,res=x.res;
        if(u==e)
        {
            printf("%d\n",cost);
            return ;
        }
        if(res<cap&&(dp[u][res+1]==0||dp[u][res+1]>cost+val[u]))//如果多加1单位油，能够花费更少
        {
            dp[u][res+1]=cost+val[u];
            q.push((node){u,dp[u][res+1],res+1});
        }
        for(int i=head[u]; i!=-1; i=edg[i].to)//更新与此节点相邻的节点
        {
            int v=edg[i].v,dist=edg[i].dist;
            if(res<dist)continue;//当前油量不够到达下一个节点
            if(dp[v][res-dist]==0||dp[v][res-dist]>cost)//能够达到下一个节点，而且花费更少
            {
                dp[v][res-dist]=cost;
                q.push((node){v,cost,res-dist});
            }
        }
    }
    printf("impossible\n");
    return ;
}
int main()
{
    while( scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=0; i<n; i++)
            scanf("%d",&val[i]);
        int a,b,c;
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c);
            addedge(b,a,c);
        }
        int q;
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d%d%d",&cap,&s,&e);
            bfs();
        }
    }
    return 0;
}