QBTICKET - Mua vé tàu hoả
Tác giả: ll931110
Ngôn ngữ: Pascal
Program QBTICKET;
Const
input = '';
output = '';
maxn = 100000;
maxl = 1000000000;
maxv = maxn * maxl;
Var
l,c: array[1..3] of longint;
heap: array[1..maxn] of longint;
a,d: array[1..maxn + 1] of int64;
n,s,f,nHeap: longint;
Procedure init;
Var
fi: text;
i,t: longint;
Begin
Assign(fi, input);
Reset(fi);
Readln(fi,l[1],l[2],l[3],c[1],c[2],c[3]);
Read(fi, n, s, f);
If s > f then
Begin
t:= s;
s:= f;
f:= t;
End;
a[1]:= 0;
For i:= 2 to n do readln(fi, a[i]);
a[n + 1]:= maxv;
Close(fi);
End;
Procedure update(v: longint);
Var
child,parent: longint;
Begin
inc(nHeap);
child:= nHeap;
parent:= child div 2;
While (parent > 0) and (heap[parent] > v) do
Begin
heap[child]:= heap[parent];
child:= parent;
parent:= child div 2;
End;
heap[child]:= v;
End;
Function pop: longint;
Var
r,c,v: longint;
Begin
pop:= heap[1];
v:= heap[nHeap];
dec(nHeap);
r:= 1;
While r * 2 <= nHeap do
Begin
c:= r * 2;
If (c < nHeap) and (heap[c + 1] < heap[c]) then inc(c);
If heap[c] >= v then break;
heap[r]:= heap[c];
r:= c;
End;
heap[r]:= v;
End;
Procedure solve;
Var
i,u,v: longint;
Begin
nHeap:= 0;
For i:= 1 to n do d[i]:= maxv;
d[s]:= 0;
update(s);
Repeat
u:= pop;
v:= u;
For i:= 1 to 3 do
Begin
While (a[u] + l[i] >= a[v]) and (v <= f) do inc(v);
dec(v);
If d[v] = maxv then update(v);
If d[v] > d[u] + c[i] then d[v]:= d[u] + c[i];
End;
Until nHeap = 0;
End;
Procedure printresult;
Var
fo: text;
Begin
Assign(fo, output);
Rewrite(fo);
Writeln(fo, d[f]);
Close(fo);
End;
Begin
init;
solve;
printresult;
End.