fork download
copy 
  1. const MaxN = 1000001;
  2. var n,m,s,f:longint;
  3.     c,d,q,p:array[0..MaxN] of int64;
  4.     a,b,t,kq:array[0..MaxN] of longint;
  5. procedure init;
  6. var i,x,y:longint; z:int64;
  7. begin
  8.         read(n,m,s,f);
  9.         for i:=1 to m do
  10.         begin
  11.                 read(x,y,z);
  12.                 a[i]:=x; b[i]:=y; c[i]:=z;
  13.                 a[i+m]:=y; b[i+m]:=x; c[i+m]:=z;
  14.         end;
  15. end;
  16. procedure sort(l,r:longint);
  17. var i,j,x:longint; y:int64;
  18. begin
  19.         i:=l; j:=r; x:=a[(i+j) div 2];
  20.         repeat
  21.                 while a[i]<x do inc(i);
  22.                 while x<a[j] do dec(j);
  23.                 if not (i>j) then
  24.                 begin
  25.                         y:=a[i]; a[i]:=a[j]; a[j]:=y;
  26.                         y:=b[i]; b[i]:=b[j]; b[j]:=y;
  27.                         y:=c[i]; c[i]:=c[j]; c[j]:=y;
  28.                         inc(i); dec(j);
  29.                 end;
  30.         until i>j;
  31.         if i<r then sort(i,r);
  32.         if l<j then sort(l,j);
  33. end;
  34. function find(x:longint):longint;
  35. var l,r,g,vt:longint;
  36. begin
  37.         l:=1; r:=m*2; vt:=0;
  38.         while l<=r do
  39.         begin
  40.                 g:=(l+r) div 2;
  41.                 if a[g]>=x then
  42.                 begin
  43.                         vt:=g; r:=g-1;
  44.                 end else l:=g+1;
  45.         end;
  46.         exit(vt);
  47. end;
  48. procedure Gao_Pink;
  49. var i,u,v,l,r:longint; du,dv:int64; 
  50. begin
  51.         for i:=1 to n do d[i]:=high(int64);
  52.         l:=0; r:=1; d[s]:=0; q[r]:=s; p[r]:=0;
  53.         while l<r do
  54.         begin
  55.                 inc(l); u:=q[l]; du:=p[l];
  56.                 for i:=find(u) to m*2+2 do
  57.                 if a[i]=u then
  58.                 begin
  59.                         v:=b[i]; dv:=c[i];
  60.                         if d[v]>du+dv then
  61.                         begin
  62.                                 d[v]:=du+dv; inc(r);
  63.                                 t[v]:=u; q[r]:=v; p[r]:=d[v];
  64.                         end;
  65.                 end else break;
  66.         end;
  67. end;
  68. procedure query;
  69. var i,p:longint;
  70. begin
  71.         writeln(d[f]); p:=0;
  72.         while f>0 do
  73.         begin
  74.                 inc(p); kq[p]:=f; f:=t[f];
  75.         end;
  76.         for i:=p downto 1 do write(kq[i],' ');
  77. end;
  78. BEGIN
  79.         init; sort(1,m*2); Gao_Pink; query;
  80. END.
Success #stdin #stdout 0.01s 14536KB
comments (?)
stdin
copy 
3 3 1 3
1 2 3
1 3 5
2 3 1
stdout
copy 
4
1 2 3
https://ideone.com/var54P
language:
Pascal (fpc 3.0.4)
created:
2 years ago
visibility:
secret

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!