题意：

已知每一个点的加油站的油价单位价格（即点权）。每条路的长度（边权）。

有q个询问。每一个询问包含起点s、终点e和油箱容量。

问从起点走到终点的最小花费。假设不可达输出impossible，否则输出最小的旅途费用。

算法：

事实上要分析状态= =感觉就像是dp。

最直接的想法是  每到一个点都加上要走到下一个点所须要的油量。可是走的路不同，究竟怎么处理加多少的问题呢?

因此想到分解状态。即拆点。每到一个点都+1单位的油量，然后把这个状态增加队列。另外假设如今油箱内的油足够达到下一点，

则更新状态，把新状态增加优先队列。

dp[i][j]表示到第i个城市剩余油量为j的花费。

简单的说。就是优先队列优化的最短路算法多了一维。

为了把全部可能的状态考虑到。

每到一个点仅仅有两种操作：1、加一单位的油   2、更新能走到的下一个点。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#define maxm 10010

#define maxn 1010

using namespace std;

struct Edge

{

    int to,val,next;

}edge[maxm*2];

struct node

{

    int id,cost,oil;

    bool operator <(const node &b) const

    {

        return cost > b.cost;

    }

};

bool vis[maxn][110];

int cnt,head[maxn],dp[maxn][110],ans,st,ed,cap,p[maxn];

priority_queue<node> q;

void add(int x,int y,int z)

{

    edge[cnt].to = y;

    edge[cnt].val = z;

    edge[cnt].next = head[x];

    head[x] = cnt++;

}

bool bfs()

{

    memset(dp,0x3f,sizeof(dp));

    memset(vis,0,sizeof(vis));

    while(!q.empty())

        q.pop();

    int id,oil,cost;

    ans = 0;

    dp[st][0] = 0;

    node now,cur,next;

    now.id = st;

    now.cost = 0;

    now.oil = 0;

    q.push(now);

    while(!q.empty())

    {

        cur = q.top();

        q.pop();

        id = cur.id,oil = cur.oil,cost = cur.cost;

        if(id == ed)

        {

            ans = cost;

            return true;

        }

        if(vis[id][oil]) continue;

        vis[id][oil] = true;

        if(oil < cap)

        {

            next.id = id;

            next.cost = cost+p[id];

            next.oil = oil+1;

            if(dp[next.id][next.oil]>next.cost && !vis[next.id][next.oil])

            {

                dp[next.id][next.oil] = next.cost;

                q.push(next);

            }

        }

        for(int i=head[id];i!=-1;i = edge[i].next)

        {

            int u = edge[i].to;

            int w = edge[i].val;

            if(oil>=w && dp[u][oil-w]>cur.cost && !vis[u][oil-w])

            {

                next.oil = oil-w;

                next.id = u;

                next.cost = cost;

                dp[u][next.oil] = next.cost;

                q.push(next);

            }

        }

    }

    return false;

}

int main()

{

    int n,m,u,v,l,que;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        memset(head,-1,sizeof(head));

        cnt = 0;

        for(int i=0;i<n;i++)

            scanf("%d",&p[i]);

        for(int i=0;i<m;i++)

        {

            scanf("%d%d%d",&u,&v,&l);

            add(u,v,l);

            add(v,u,l);

        }

        scanf("%d",&que);

        while(que--)

        {

            scanf("%d%d%d",&cap,&st,&ed);

            if(bfs())

                printf("%d\n",ans);

            else printf("impossible\n");

        }

    }

    return 0;

}