题目大意：有N个站点，每个站点供应油的价格为Pi，有M条路，每条路耗油量为Ci。现在又Q个询问，求出，当坦克在S点，油量为0，要到达T点，油箱容量为V的最小价格。

分析：有点像dij，用一个数组used[ i ][ j ]记录，第i个站点，油量为j的情况是否出现过。用优先队列每次选出花费最小的节点更新。入队有2种情况：

1.当可以走向下一个节点时

2.当可以再买1升汽油时（保证每种情况都考虑到，DP的思想）

PS：代码写烂了...好慢

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
#define MAXE 20020
#define MAXN 1010
#define SET(a,b) memset(a,b,sizeof(a))

int next[MAXE],p[MAXE],c[MAXE],st[MAXN],e;
int used[MAXN][110],price[MAXN];

void add(int a,int b,int d)
{
    next[e]=st[a];
    p[e]=b;
    c[e]=d;
    st[a]=e++;
}

struct Node
{
    int num,fuel,cost;
    Node(int num,int fuel,int cost):num(num),fuel(fuel),cost(cost){}
    friend bool operator < (Node a,Node b)
    {
        return a.cost>b.cost;
    }
};


int work(int S,int T,int C)
{
    priority_queue<Node> Q;
    SET(used,0);
    Q.push(Node(S,0,0));
    used[S][0]=1;
    while(!Q.empty())
    {
        int u=Q.top().num,f=Q.top().fuel,m=Q.top().cost;
        if(u==T)return m;
        Q.pop();
        for(int v=st[u];v!=-1;v=next[v])
        {
            if(f>=c[v])
            {
                if(!used[p[v]][f-c[v]])
                {
                    used[p[v]][f-c[v]]=1;
                    Q.push(Node(p[v],f-c[v],m));
                }
            }
        }
        if(f+1<=C&&!used[u][f+1])Q.push(Node(u,f+1,m+price[u]));
    }
    return -1;
}

int main()
{
    int N,M;
    SET(st,-1);e=0;
    scanf("%d%d",&N,&M);
    int i,j,k;
    for(i=1;i<=N;i++)scanf("%d",price+i);
    for(i=1;i<=M;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        x++,y++;
        add(x,y,z);
        add(y,x,z);
    }
    int P;
    scanf("%d",&P);
    for(i=1;i<=P;i++)
    {
        int S,T,C;
        scanf("%d%d%d",&C,&S,&T);
        S++,T++;
        int tttt=work(S,T,C);
        if(tttt==-1)printf("impossible\n");
        else printf("%d\n",tttt);
    }
    //system("pause");
    return 0;
}