题解 | #Full Tank#

在处理好输入输出之后，关键从集合的角度考虑最小花费。
决策类问题带有动态规划的思想，用第一个维度表示从起点到达的城市，第二个维度表示当前油箱剩余的油量，f[i,j]表示从起点到i城剩余油量为j的最小花费。
然后使用一个小根堆来维护这个状态，这样可以保证第一次得到终点时的状态是最优解
这道题难在无法判断在某个城市应该加多少油，因此我们一点一点的加。每次加一单位的油并加入优先队列，直到到达终点即可，剩下的就很像最短路里的堆优化dijkstra了

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define x first
#define y second
#define N 1010
#define M 10010

int n,m;
int S,T,c;
int pi[M];
int e[M*2],ne[M*2],h[N],w[2*M],idx=0;
int f[N][N];  //动态规划用
bool st[N][110];

struct Cost{
    int city,fl,s; //到达的城市，剩余的油量，花费
    bool operator<(const Cost W)const{
        return W.s<s;
    }
};

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c;
    ne[idx]=h[a],h[a]=idx++;
}

int bfs(int S,int T,int c){
    memset(st,0,sizeof st);
    memset(f,0x3f,sizeof f);

    priority_queue<Cost> heap;
    heap.push({S,0,0});
    f[S][0]=0;

    while(heap.size()){
        auto u=heap.top();heap.pop();
        int city = u.city , fuel = u.fl , spent = u.s ;

        if(st[city][fuel]) continue;
        st[city][fuel]=true;

        if(city==T){
            return spent;
        }

        for(int i=h[city];~i;i=ne[i]){
            int j=e[i];
            if(fuel>=w[i]&&f[city][fuel]<f[j][fuel-w[i]]){
                f[j][fuel-w[i]]=f[city][fuel];
                heap.push({j,fuel-w[i],f[j][fuel-w[i]]});
            }
        }

        if(fuel<c){
            if(f[city][fuel]+pi[city]<f[city][fuel+1]){
                f[city][fuel+1]=f[city][fuel]+pi[city];
                heap.push({city,fuel+1,f[city][fuel+1]});
            }
        }

    }
    return -1;
}

int main(){
    memset(h,-1,sizeof h);

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

    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c),add(b,a,c);
    }

    int q;
    scanf("%d",&q);
    while(q--){
        scanf("%d%d%d",&c,&S,&T);
        int res=bfs(S,T,c);
        if(res==-1) puts("impossible");
        else printf("%d\n",res);
    }
    return 0;
}