fork download
copy 
  1. var
  2.     tot,i,j,n,g,m,k,l,t,x,aa,bb,tmp,tmp2,s,head,tail:longint;
  3.     a:array[-2..6000100]of record
  4.       tt,vv,next:longint;
  5.     end;
  6.     b:array[-2..2000100]of boolean;
  7.     d:array[-2..2000100]of longint;
  8.     q:array[1..2000100]of longint;
  9.   function max(x,y:longint):longint;
  10.     begin
  11.       if x>y then exit(x);
  12.       exit(y);
  13.     end;
  14.   procedure specialdoit;
  15.     begin
  16.       k:=maxlongint;
  17.       for i:=1 to max(n,m)-1 do
  18.         begin
  19.           read(x);
  20.           if x<k then k:=x;
  21.         end;
  22.       writeln(k);
  23.       close(input);
  24.       close(output);
  25.       halt;
  26.     end;
  27.   procedure linkit(z,zz,v:longint);
  28.     begin
  29.       if a[z].tt=0 then
  30.         begin
  31.           a[z].tt:=zz;
  32.           a[z].vv:=v;
  33.         end
  34.       else begin
  35.         inc(tot);
  36.         a[tot].next:=a[z].next;
  37.         a[tot].tt:=zz;
  38.         a[tot].vv:=v;
  39.         a[z].next:=tot;
  40.       end;
  41.       if a[zz].tt=0 then
  42.         begin
  43.           a[zz].tt:=z;
  44.           a[zz].vv:=v;
  45.         end
  46.       else begin
  47.         inc(tot);
  48.         a[tot].next:=a[zz].next;
  49.         a[tot].tt:=z;
  50.         a[tot].vv:=v;
  51.         a[zz].next:=tot;
  52.       end;
  53.     end;
  54.   procedure spfa;
  55.     var
  56.       i,j:longint;
  57.     begin
  58.       head:=0;tail:=1;
  59.       q[1]:=-1;d[-1]:=0;
  60.       while head<>tail do
  61.         begin
  62.           inc(head);
  63.           if head=2000001 then head:=1;
  64.           k:=q[head];
  65.           x:=k;
  66.           while x<>0 do
  67.             begin
  68.               tmp:=a[x].vv;
  69.               g:=a[x].tt;
  70.               if d[k]+tmp<d[g] then
  71.                 begin
  72.                   d[g]:=d[k]+tmp;
  73.                   if not b[g] then
  74.                     begin
  75.                       b[g]:=true;
  76.                       inc(tail);
  77.                       if tail=2000001 then tail:=1;
  78.                       q[tail]:=g;
  79.                     end;
  80.                 end;
  81.               x:=a[x].next;
  82.             end;
  83.           b[k]:=false;
  84.         end;
  85.     end;
  86.   begin
  87.     s:=-1;
  88.     t:=-2;
  89.     tot:=2000000;
  90.     readln(n,m);
  91.     if (n=1)or(m=1) then specialdoit;
  92.  
  93.     for i:=1 to n do
  94.       for j:=1 to m-1 do
  95.         begin
  96.           tmp:=(i-1)*(m-1)*2;
  97.           tmp2:=(i-2)*(m-1)*2;
  98.           read(x);
  99.           if i=1 then begin
  100.             aa:=t;
  101.             bb:=j*2;
  102.             linkit(aa,bb,x);
  103.           end
  104.           else if i=n then begin
  105.             aa:=s;
  106.             bb:=tmp2+j*2-1;
  107.             linkit(aa,bb,x);
  108.           end
  109.           else begin
  110.             aa:=tmp2+j*2-1;
  111.             bb:=tmp+j*2;
  112.             linkit(aa,bb,x);
  113.           end;
  114.         end;
  115.  
  116.     for i:=1 to n-1 do
  117.       for j:=1 to m do
  118.         begin
  119.           tmp:=(i-1)*(m-1)*2;
  120.           read(x);
  121.           if j=1 then begin
  122.             aa:=s;
  123.             bb:=tmp+j*2-1;
  124.             linkit(aa,bb,x);
  125.           end
  126.           else if j=m then begin
  127.             aa:=t;
  128.             bb:=tmp+(j-1)*2;
  129.             linkit(aa,bb,x);
  130.           end
  131.           else begin
  132.             aa:=tmp+(j-1)*2;
  133.             bb:=tmp+j*2-1;
  134.             linkit(aa,bb,x);
  135.           end;
  136.         end;
  137.  
  138.     for i:=1 to n-1 do
  139.       for j:=1 to m-1 do
  140.         begin
  141.           tmp:=(i-1)*(m-1)*2;
  142.           read(x);
  143.           aa:=tmp+j*2;
  144.           bb:=aa-1;
  145.           linkit(aa,bb,x);
  146.         end;
  147.     fillchar(d,sizeof(d),11);
  148.     spfa;
  149.     write(d[t])
  150.   end.
Success #stdin #stdout 0s 88192KB
comments (?)
stdin
copy 
3 4

5 6 4

4 3 1

7 5 3

5 6 7 8

8 7 6 5

5 5 5

6 6 6
stdout
copy 
14
https://ideone.com/4omPYJ
language:
Pascal (fpc 3.0.4)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!