题目大意
给定一张 \(n\) 个点，\(m\) 条边的连通无向图，在每个点有一个加油站，油价为该点的点权，每条边的油耗为该边的边权。现给出若干询问，问一辆油箱容量为 \(c\) 的车子是否能从 \(s\) 开到 \(e\)，如果可以，求出最小所需的钱。
思路分析
看到这种有图有权求最小消耗的题，我们首先考虑最短路。
第一步，观察数据范围。
我们发现 \(c\) 较小，\(n\) 也不算大，这启示我们可以设计一个由剩余油量和点构成的二维状态，又因为存在多组询问，我们无法接受时间复杂度为 \(O(nmT)\) 的 SPFA，所以考虑用 Dijkstra。
第二步，考虑状态转移。
在跑正常的最短路时，对于每一个已经更新完毕的点，我们都借助它来更新其他点，但在这题中，我们设计了二维的状态，在每一个点都有两种操作：扣油去往其他的点或是原地不动花钱加油，我们需要同时考虑这两种操作。
具体的说，对于每一个二维的点 \((x,m)\)（\(x\) 表示当前位置，\(m\) 表示当前油量），我们可以用这个点更新点 \((x,m+1)(m+1\le c)\) 和所有的 \((y,m-w_{xy})(y\in \text{to}_x)\)，更新方法类似于 Dijkstra。
然后就可以轻松写出代码了！
代码
#include <bits/stdc++.h>
using namespace std;
const int N=2010,M=20020,C=105;//点数，边数，最大油箱容量
int to[M],nxt[M],head[N],w[M],p[N];//图，边权，点权
int idx,n,m,c,s,e,in1,in2,in3,ans,Q;
int vis[N][C],dis[N][C];//二维的点，vis表示是否访问，dis是距离
struct node{int x,cost,you;}now;
bool operator < (node a,node b){return a.cost>b.cost;}//在优先队列中按所花的钱排序
priority_queue <node> q;
void add(int u,int v,int c){idx++;to[idx]=v;w[idx]=c;nxt[idx]=head[u];head[u]=idx;}
int bfs(int s){
while(!q.empty()) q.pop();//一定要清空！！！
memset(vis,0,sizeof vis);//初始化
memset(dis,0x3f,sizeof dis);
q.push(node{s,0,0});
dis[s][0]=0;
while(!q.empty()){
now=q.top();q.pop();
if(now.x==e) return now.cost;//到达终点
if(vis[now.x][now.you]) continue;
vis[now.x][now.you]=1;
if(now.you<c) //如果当前油箱没有满
if(dis[now.x][now.you+1]>now.cost+p[now.x]){
dis[now.x][now.you+1]=now.cost+p[now.x];//更新状态
q.push(node{now.x,now.cost+p[now.x],now.you+1});//加油，入队
}
for(int i=head[now.x];i;i=nxt[i]){
if(now.you<w[i]) continue;//无法通过
if(dis[to[i]][now.you-w[i]]>now.cost){//可以通过，更新状态
dis[to[i]][now.you-w[i]]=now.cost;
q.push(node{to[i],now.cost,now.you-w[i]});//扣油，入队
}
}
}
return -1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&p[i]);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&in1,&in2,&in3);
in1++;in2++;//点从0到n-1，我们统一加1
add(in1,in2,in3);add(in2,in1,in3);
}
scanf("%d",&Q);
while(Q--){
scanf("%d%d%d",&c,&s,&e);
s++;e++;
ans=bfs(s);
if(ans==-1) puts("impossible");//无解
else printf("%d\n",ans);
}
return 0;
}