题目描述&数据范围:
有N个城市（编号0、1…N-1）和M条道路，构成一张无向图。
在每个城市里边都有一个加油站，不同的加油站的单位油价不一样。
现在你需要回答不超过100个问题，在每个问题中，请计算出一架油箱容量为C的车子，从起点城市S开到终点城市E至少要花多少油钱？
注意： 假定车子初始时油箱是空的。
输入格式
第一行包含两个整数N和M。
第二行包含N个整数，代表N个城市的单位油价，第i个数即为第i个城市的油价pi。
接下来M行，每行包括三个整数u,v,d，表示城市u与城市v之间存在道路，且车子从u到v需要消耗的油量为d。
接下来一行包含一个整数q，代表问题数量。
接下来q行，每行包含三个整数C、S、E，分别表示车子油箱容量、起点城市S、终点城市E。
输出格式
对于每个问题，输出一个整数，表示所需的最少油钱。
如果无法从起点城市开到终点城市，则输出”impossible”。
每个结果占一行。
数据范围
1≤N≤1000,
1≤M≤10000,
1≤pi≤100,
1≤d≤100,
1≤C≤100
题目中有N个城市(最多1k...dij怎么写呢?因为含有两种元素一种是边的距离第二种是油量.所以我们可以把{所付代价,到达点,油量}看成一个集合.起点是{0,S,0},终点就是{ans,E,0}.我们每次进行如下操作即可覆盖所有情况,完成dij.

首先把值定为inf,每次取出代价最少的答案.然后进行扩展,把最少的扩展了就不会再扩展了(因为边权为正),然后进行下一步操作.
扩展分为2步即可覆盖所有情况.
1.把当前点的油量+1然后放进堆,油量加1,代价更新,路径不变.
2.假如当前油量可以直接走完现在的路程,那么就直接走完一段路,油量减少路径更新.

上面即覆盖了最大的情况了,考虑建边很多,我们使用堆优化的dij.我们大概点数为NC(最多的情况啦)1e5.然后边数为100^1000.复杂度就是1e8log100(4)
大概那么多了--当然肯定不会有这么多,2s,dij肯定能过的.
下面就是代码实现了

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
const int C=1e2+5;
int p[N];//每个点的油价
bool st[N][C];
int dis[N][C];
struct node
{
    int val,pos,oil;//当前位子代价,当前位子,剩余油量
    bool operator<(const node &A)const{
        return val>A.val;
    }
};
struct vv
{
    int to,len;//要到达的地方,以及边的长度
};
vector<vv>v[N];
int dij(int a,int b,int c)//a起点 b终点 c油箱容量
{
    memset(st,false,sizeof st);
    memset(dis,0x3f,sizeof dis);
    priority_queue<node>q;
    q.push({0,a,0});//先把起点推进去.三种元素{所付代价,到达点,油量}
    dis[a][0]=0;
    while(q.size())
    {
        auto t=q.top();//取出堆顶元素
        q.pop();
        if(t.pos==b) return t.val;//假如堆顶是终点就直接返回答案.
        if(st[t.pos][t.oil]) continue;//假如记录过就直接跳过
        st[t.pos][t.oil]=true;
        if(t.oil<c)//假如现在还可以+1升油
        {
            if(dis[t.pos][t.oil+1]>t.val+p[t.pos]) 
            {
                q.push({t.val+p[t.pos],t.pos,t.oil+1});
                dis[t.pos][t.oil+1]=t.val+p[t.pos];
            }
        }
        for(int i=0;i<v[t.pos].size();i++)//假如现在的油量还可以走到下一个城市
        {
            int j=v[t.pos][i].to;//我要去的城市
            if(t.oil>=v[t.pos][i].len)//假如我现在的油量已经大于这条路的长度了,那么我就可以去.
            {
                if(dis[j][t.oil-v[t.pos][i].len]>t.val) 
                {
                    q.push({t.val,j,t.oil-v[t.pos][i].len});
                    dis[j][t.oil-v[t.pos][i].len]=t.val;
                } 
            }
        }
    }
    return -1;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);//n个点 m条边
    for(int i=0;i<n;i++) scanf("%d",&p[i]);//n个点的代价
    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);//a b建条长度为c的边
        v[a].push_back(vv{b,c});
        v[b].push_back(vv{a,c});
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int a,b,c;
        scanf("%d%d%d",&c,&a,&b);//查询a为起点b为终点油的容量为c的最小花费
        if(dij(a,b,c)==-1) puts("impossible");
        else               printf("%d\n",dij(a,b,c));
    }
    return 0;
}