fork download
copy 
  1. uses    math;
  2. const   finp='';
  3.         fout='';
  4.         maxc=round(1e9);
  5.         maxn=20005;
  6. type    point=^ptype;
  7.         ptype=record
  8.          v,info:longint;
  9.          link:point;
  10.          end;
  11.         bg=record
  12.          key,cs:longint;
  13.          end;
  14.  
  15. var     fi,fo:text;
  16.         g,g1:array[1..maxn] of point;
  17.         d,pos:array[0..maxn,1..2] of longint;
  18.         heap:array[1..2*maxn] of bg;
  19.         free:array[0..maxn,1..2] of boolean;
  20.         i,n,m,s,t,k,u,v,x,u1,nheap,j,test,y:longint;
  21.  
  22. Procedure them(u1,u2:longint);
  23. var     p:point;
  24. begin
  25.         new(p);
  26.         p^.v:=u2;
  27.         p^.info:=x;
  28.         p^.link:=g[u];
  29.         g[u]:=p;
  30. end;
  31.  
  32. Procedure them1(u1,u2:longint);
  33. var     p:point;
  34. begin
  35.         new(p);
  36.         p^.v:=u2;
  37.         p^.info:=x;
  38.         p^.link:=g1[u];
  39.         g1[u]:=p;
  40. end;
  41.  
  42. Procedure update(v,u:longint);
  43. var     parent,child:longint;
  44. begin
  45.         child:=pos[v,u];
  46.         if child=0 then
  47.          begin
  48.                 inc(nheap);child:=nheap;
  49.          end;
  50.         parent:=child div 2;
  51.         while (parent>0) and (d[heap[parent].key,heap[parent].cs]>d[v,u]) do
  52.          begin
  53.                 heap[child]:=heap[parent];
  54.                 pos[heap[child].key,heap[child].cs]:=child;
  55.                 child:=parent;
  56.                 parent:=child div 2;
  57.          end;
  58.         heap[child].key:=v;
  59.         heap[child].cs:=u;
  60.         pos[v,u]:=child;
  61. end;
  62.  
  63. Function pop:longint;
  64. var     r,c,v,v1:longint;
  65. begin
  66.         pop:=heap[1].key;u1:=heap[1].cs;
  67.         v:=heap[nheap].key;v1:=heap[nheap].cs;
  68.         dec(nheap);
  69.         r:=1;
  70.         while r*2<=nheap do
  71.          begin
  72.                 c:=r*2;
  73.                 if (c<nheap) and (d[heap[c+1].key,heap[c+1].cs]<d[heap[c].key,heap[c].cs]) then inc(c);
  74.                 if d[v,v1]<=d[heap[c].key,heap[c].cs] then break;
  75.                 heap[r]:=heap[c];
  76.                 pos[heap[r].key,heap[r].cs]:=r;
  77.                 r:=c;
  78.          end;
  79.         heap[r].key:=v;
  80.         heap[r].cs:=v1;
  81.         pos[v,v1]:=r;
  82. end;
  83.  
  84. Procedure dijkstra;
  85. var     p:point;
  86. begin
  87.         for i:=1 to n do
  88.          for j:=1 to 2 do free[i,j]:=false;
  89.         for i:=1 to n do
  90.          for j:=1 to 2 do pos[i,j]:=0;
  91.         for i:=1 to n do
  92.          for j:=1 to 2 do d[i,j]:=maxc;
  93.         nheap:=0;
  94.         d[s,1]:=0;
  95.         update(s,1);
  96.         repeat
  97.                 u:=pop;
  98.                 if (u=t) and (u=0) then break;
  99.                 free[u,u1]:=true;
  100.                 if u1=1 then
  101.                  begin
  102.                         p:=g[u];
  103.                         while p<>nil do
  104.                          begin
  105.                                 v:=p^.v;
  106.                                 if not free[v,1] and (d[v,1]>d[u,1]+p^.info) then
  107.                                  begin
  108.                                         d[v,1]:=d[u,1]+p^.info;
  109.                                         update(v,1);
  110.                                  end;
  111.                                 p:=p^.link;
  112.                          end;
  113.                         p:=g1[u];
  114.                         while p<>nil do
  115.                          begin
  116.                                 v:=p^.v;
  117.                                 if not free[v,2] and (d[v,2]>d[u,1]+p^.info) then
  118.                                  begin
  119.                                         d[v,2]:=d[u,1]+p^.info;
  120.                                         update(v,2);
  121.                                  end;
  122.                                 p:=p^.link;
  123.                          end;
  124.                  end else
  125.                  begin
  126.                         p:=g[u];
  127.                         while p<>nil do
  128.                          begin
  129.                                 v:=p^.v;
  130.                                 if not free[v,2] and (d[v,2]>d[u,2]+p^.info) then
  131.                                  begin
  132.                                         d[v,2]:=d[u,2]+p^.info;
  133.                                         update(v,2);
  134.                                  end;
  135.                                 p:=p^.link;
  136.                          end;
  137.                  end;
  138.                 if nheap=0 then break;
  139.         until false;
  140.         if (d[t,1]=maxc) and (d[t,2]=maxc) then writeln(fo,-1) else
  141.          writeln(fo,min(d[t,1],d[t,2]));
  142. end;
  143.  
  144. BEGIN
  145.         assign(fi,finp);reset(fi);
  146.         assign(fo,fout);rewrite(fo);
  147.         readln(fi,test);
  148.         for y:=1 to test do
  149.          begin
  150.                 readln(fi,n,m,k,s,t);
  151.                 for i:=1 to n do
  152.                  begin
  153.                         g[i]:=nil;g1[i]:=nil;
  154.                  end;
  155.                 for i:=1 to m do
  156.                  begin
  157.                         readln(fi,u,v,x);
  158.                         them(u,v);
  159.                  end;
  160.                 for i:=1 to k do
  161.                  begin
  162.                         readln(fi,u,v,x);
  163.                         them1(u,v);
  164.                         them1(v,u);
  165.                  end;
  166.                 dijkstra;
  167.          end;
  168.         close(fi);close(fo);
  169. END.
  170.  
  171.  
  172.  
  173.  
Success #stdin #stdout 0s 1268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WPGp3F
language:
Pascal (fpc 3.0.4)
created:
8 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!