【题意】
给定n(n<=1000)个编号为0..n-1加油站的每单位油价格，再给定m(m<=10000)条边，并给出通过其所需油(<=100)，询问q(q<=100)次，询问油箱容量为c(c<=100)时，s到e的所需最小费用
【输入】
第一行两个数字n、m
接下来一行n个数字表示每个加油站的单位油价
接下来m行每行三个数字u、v、d描述一条边
接下来一行一个数q表示询问数
之后q行每行描述一个询问c、s、e
【输出】
对于每个询问，输出一个数字表示最小费用，若不存在则输出'impossible'
heap+dijkstra
用dis[i][j]表示到达i节点油箱内还有j单位的油的最小费用
对于每次增光，分为两种，向别的节点前进或使油箱增加1单位的油
注意对堆的清空
program poj3635;
var
ok:boolean;
tot,now,who,q,n,m,i,j,k,u,v,d,c,s,e:longint;
yes:array [0..1001] of boolean;
root,p:array [0..1001] of longint;
next,cost,point:array [0..20001] of longint;
status,heap:array [0..200001] of longint;
rank,dis:array [0..1001,0..101] of longint;
procedure swap (var a,b:longint);
var
i:longint;
begin
i:=a;
a:=b;
b:=i;
end;
procedure connect (u,v,d:longint);
begin
inc(tot);
point[tot]:=v;
cost[tot]:=d;
next[tot]:=root[u];
root[u]:=tot;
end;
procedure delete (who,now:longint);
var
i:longint;
begin
if rank[who,now]=0 then exit;
if rank[who,now]=tot then
begin
heap[tot]:=0;
status[tot]:=0;
rank[who,now]:=0;
dec(tot);
exit;
end;
i:=rank[who,now];
swap(rank[who,now],rank[heap[tot],status[tot]]);
swap(heap[i],heap[tot]);
swap(status[i],status[tot]);
heap[tot]:=0;
status[tot]:=0;
rank[who,now]:=0;
dec(tot);
if (i>1)and(dis[heap[i div 2],status[i div 2]]>dis[heap[i],status[i]]) then
while (i>1)and(dis[heap[i div 2],status[i div 2]]>dis[heap[i],status[i]]) do
begin
swap(rank[heap[i div 2],status[i div 2]],rank[heap[i],status[i]]);
swap(heap[i],heap[i div 2]);
swap(status[i],status[i div 2]);
i:=i div 2;
end
else
while (dis[heap[i*2],status[i*2]]<dis[heap[i],status[i]])
or(dis[heap[i*2+1],status[i*2+1]]<dis[heap[i],status[i]]) do
if dis[heap[i*2],status[i*2]]<dis[heap[i*2+1],status[i*2+1]] then
begin
swap(rank[heap[i],status[i]],rank[heap[i*2],status[i*2]]);
swap(heap[i*2],heap[i]);
swap(status[i*2],status[i]);
i:=i*2;
end
else
begin
swap(rank[heap[i],status[i]],rank[heap[i*2+1],status[i*2+1]]);
swap(heap[i*2+1],heap[i]);
swap(status[i*2+1],status[i]);
i:=i*2+1;
end;
end;
procedure insert (who,now:longint);
var
i:longint;
begin
inc(tot);
heap[tot]:=who;
status[tot]:=now;
rank[who,now]:=tot;
i:=tot;
while (i>1)and(dis[heap[i div 2],status[i div 2]]>dis[heap[i],status[i]]) do
begin
swap(rank[heap[i div 2],status[i div 2]],rank[who,now]);
swap(heap[i],heap[i div 2]);
swap(status[i],status[i div 2]);
i:=i div 2;
end;
end;
procedure heap_dijkstra;
begin
while tot>0 do
begin
now:=status[1];
who:=heap[1];
if who=e then
begin
ok:=true;
writeln(dis[who,now]);
exit;
end;
delete(who,now);
if (now<c)and(dis[who,now+1]>dis[who,now]+p[who]) then
begin
delete(who,now+1);
dis[who,now+1]:=dis[who,now]+p[who];
insert(who,now+1);
end;
k:=root[who];
while k<>0 do
begin
if (now>=cost[k])and(dis[who,now]<dis[point[k],now-cost[k]]) then
begin
delete(point[k],now-cost[k]);
dis[point[k],now-cost[k]]:=dis[who,now];
insert(point[k],now-cost[k]);
end;
k:=next[k];
end;
end;
end;
function dfs (now:longint):boolean;
var
i:longint;
begin
if now=e then exit(true);
yes[now]:=true;
i:=root[now];
while i<>0 do
begin
if (not yes[point[i]])and(cost[i]<=c)and(dfs(point[i])) then exit(true);
i:=next[i];
end;
exit(false);
end;
begin
read(n,m);
for i:=1 to n do
read(p[i]);
tot:=0;
for i:=1 to m do
begin
read(u,v,d);
inc(u);
inc(v);
connect(u,v,d);
connect(v,u,d);
end;
read(q);
while q<>0 do
begin
dec(q);
fillchar(yes,sizeof(yes),false);
read(c,s,e);
inc(s);
inc(e);
if not dfs(s) then
begin
writeln('impossible');
continue;
end;
fillchar(heap,sizeof(heap),0);
fillchar(dis,sizeof(dis),63);
fillchar(rank,sizeof(rank),0);
tot:=0;
dis[s,0]:=0;
insert(s,0);
ok:=false;
heap_dijkstra;
end;
end.