Description
已知每个点的加油站的油价单价（即点权），每条路的长度（边权）。
有q个询问，每个询问包括起点s、终点e和油箱容量c。
问从起点走到终点的最小花费。如果不可达输出impossible，否则输出最小的旅途费用。
Solution
第一想法想到拆点，每个点拆成 0~c 那么多个点，妥妥TLE。
后来看题解想到可以进行一个最短路DP，用一个三元组 (x,y,z) 表示当前在点 x，花了 y 元，油量为 z，把这个压进优先队列，每次取出堆中 y 最少的点进行更新即可。
这里还有个奇技淫巧般的优化，就是每次取出堆顶时，不用从当前直接把油箱加满，只加 1 单位的油量就够了，这是为什么呢？其实跟飞扬的小鸟一样，为了优化时间，我们可以让 dp 从自己向自己转移，也就是说，这次只加 1 单位，下次取出时还是只加 1 单位，那么迟早会遍历所有的 n*c 状态。
哦对还要注意一点，vis 数组不要在 if 里面更新，要在取到它的时候再变为 1，不然早早变为 1 有可能让能令其更优的状态无法转移过来。
Code
// By YoungNeal
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int T;
int c,s,e;
int n,m,cnt;
];
];
][];
][];
struct Edge{
int nxt,to,dis;
}edge[];
void add(int x,int y,int z){
edge[++cnt].to=y;
edge[cnt].nxt=head[x];
edge[cnt].dis=z;
head[x]=cnt;
}
struct Node{
int now,dis,oil;
Node(,,):now(now),dis(dis),oil(oil){}
friend bool operator<(Node a,Node b){
return a.dis>b.dis;
}
};
priority_queue<Node> pq;
void dij(){
while(pq.size()) pq.pop();
pq.push(Node(s,,));
while(pq.size()){
Node p=pq.top();pq.pop();
int o=p.oil,u=p.now;
if(vis[u][o]) continue;
vis[u][o]=;
if(u==e){
printf("%d\n",p.dis);
return;
}
<=c&&!vis[u][o+]&&dis[u][o+]>dis[u][o]+val[u]){
dis[u][o+]=p.dis+val[u];
pq.push(Node(u,p.dis+val[u],o+));
}
for(int i=head[u];i;i=edge[i].nxt){
int to=edge[i].to;
int w=edge[i].dis;
if(o>=w&&!vis[to][o-w]&&dis[to][o-w]>p.dis){
dis[to][o-w]=p.dis;
pq.push(Node(to,p.dis,o-w));
}
}
}
printf("impossible\n");
}
signed main(){
scanf("%d%d",&n,&m);
;i<=n;i++) scanf("%d",&val[i]);
;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
add(x+,y+,z);
add(y+,x+,z);
}
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&c,&s,&e);
s++,e++;
memset(vis,,sizeof vis);
memset(dis,0x3f,sizeof dis);
dis[s][]=;
dij();
}
;
}