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.

Download