用的BFS+优先队列+二进制压缩状态判重+链式前向星， TLE，好像有人这样过了。。。好像要用A*算法，还不太会，所以暂时放弃。但是也学会了很多，学习了链式前向星，更深理解了BFS求最优的时候，什么时候是第一次搜到结果就是最优，该题，通过枚举加的油量，每次加一个单位，从够下一条路开始到满容量，枚举所有路，花的钱少的在队优先（头），故先出队找到目标结点的必然最优，因为后面的都是前面再加钱的。。。。好好想想。。。
#include<iostream> //链式前向星+二进制状态压缩判重+优先队列
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int prize[1002];
struct edge
{
int pre; //该边关于该点的前一条边
int to; //通哪个点
int w; //权
};
struct state
{
int dian;
int key; //二进制压缩判重
int cur_money;
int cur_fuel;
state()
{
key=0;
}
bool operator <(const state & a)const //按花费小的排序
{
return a.cur_money<cur_money;
}
};
edge bian[20002];
int head[1002]; //每个顶点的边的头指针
int mincost=0x3f3f3f3f;
void bfs(int from,int capacity,int to)
{
priority_queue<state>q;
state start;
start.dian=from;
start.key=(start.key|(1<<from));
start.cur_fuel=0;
start.cur_money=0;
q.push(start);
while(!q.empty())
{
state cur=q.top();
q.pop();
if(cur.cur_money>=mincost)continue;
if(cur.dian==to)
{
if(cur.cur_money<mincost)
mincost=cur.cur_money;
return;
//continue;
}
for(int j=head[cur.dian];j!=-1;j=bian[j].pre) //枚举边
{
if ((cur.key&(1<<bian[j].to))!=0)continue; //判重（后来知道这样判重是不对的，可以重顶点，要顶点+油量双重判重才可以）
for(int i=0;i+cur.cur_fuel<=capacity;i++) //充i油，前进。
{
state next(cur);
if(cur.cur_fuel+i<bian[j].w)continue; //不够路费的剪枝
next.cur_fuel=next.cur_fuel+i-bian[j].w;
next.cur_money=next.cur_money+i*prize[cur.dian];
if(next.cur_money>=mincost)break; //最优性剪枝
next.dian=bian[j].to;
if(next.dian==to)
{
if(next.cur_money<mincost)
mincost=next.cur_money;
break;
}
q.push(next);
next.key=(next.key|(1<<bian[j].to));
}
}
}
return ;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",&prize[i]);
int s,e,lenth;
memset(head,-1,sizeof(head));
for(int i=0;i<2*m;i++)
{
scanf("%d%d%d",&s,&e,&lenth);
bian[i].to=e;
bian[i].pre=head[s]; //head[s]:顶点s的某边，只是暂时存储，链接俩个边关系作用。
head[s]=i;
bian[i].w=lenth;
i++;
bian[i].to=s;
bian[i].pre=head[e]; //head[s]:顶点s的某边，只是暂时存储，链接俩个边关系作用。
head[e]=i;
bian[i].w=lenth;
}
/*for(int k=0;k<n;k++)
for(int j=head[k];j!=-1;j=bian[j].pre) //枚举边
{
printf("%d to %d has %d
",k,bian[j].to,bian[j].w);
}*/
int que;scanf("%d",&que);
int capacity,from,to;
while(que--)
{
mincost=0x3f3f3f3f;
scanf("%d%d%d",&capacity,&from,&to);
if(head[to]==-1||head[from]==-1){printf("impossible
");continue;}//无解
bool mark1=1;
for(int j=head[from];j!=-1;j=bian[j].pre) //枚举边
{
if(bian[j].w<=capacity){mark1=0;break;}
}
bool mark2=1;
for(int j=head[to];j!=-1;j=bian[j].pre) //枚举边
{
if(bian[j].w<=capacity){mark2=0;break;}
}
if(mark1||mark2){printf("impossible
");continue;} //无解
bfs(from,capacity,to);
if(mincost!=0x3f3f3f3f)printf("%d
",mincost);
else printf("impossible
");
}
return 0;
}