[题解]（优先队列广搜）POJ_3635_Full Tank

用二元组$(city,fuel)$即可记录所有状态，以当前花费为关键字优先队列，开数组记录直接做即可

有一个点在于每次不用枚举所有的加油数量，只需要加一即可，因为如果在加一升更优的话又会扩展出加更多油的状态，不必枚举过多

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int maxn=;

const int maxm=;

int n,m,a[maxn],c;

struct node{

    int v,w,nxt;

}e[maxm*];

struct now{

    int x,r,c;//当前城市，剩余油量，花费

    now(){}

    now(int xx,int rr,int cc){

        x=xx,r=rr,c=cc;

    }

    bool operator <(const now&a)const{

        return c>a.c;

    }

};

int head[maxn],cnt;

int d[maxn][],v[maxn][];

inline void add(int u,int v,int w){

    e[++cnt].v=v;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;

}

priority_queue<now>q;

int bfs(int st,int ed){

    while(!q.empty())q.pop();

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

    memset(v,,sizeof(v));

    q.push(now(st,,));d[st][]=;

    while(!q.empty()){

        now x=q.top();q.pop();

        v[x.x][x.r]=;

        if(x.x==ed)return x.c;

        if(!v[x.x][x.r+] && x.r+<=c && !v[x.x][x.r+] &&(d[x.x][x.r+]>d[x.x][x.r]+a[x.x])){

            d[x.x][x.r+]=d[x.x][x.r]+a[x.x];

            q.push(now(x.x,x.r+,x.c+a[x.x]));

        }

        for(int i=head[x.x];i;i=e[i].nxt){

            int y=e[i].v,z=e[i].w;

            if(x.r-z>= && !v[y][x.r-z] && d[y][x.r-z]>x.c){

                d[y][x.r-z]=x.c;

                q.push(now(y,x.r-z,x.c));

            }

        }

    }

    return -;

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<n;i++)scanf("%d",&a[i]);

    for(int i=,u,v,w;i<=m;i++){

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

        add(u,v,w);add(v,u,w);

    }

    int Q;

    scanf("%d",&Q);

    for(int i=,st,ed;i<=Q;i++){

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

        int ans=bfs(st,ed);

        if(ans!=-)

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

        else printf("impossible\n");

    }

}