fork(1) download
copy 
  1. const   fi='';
  2.         fo='';
  3.         maxn=10003;
  4.         maxc=trunc(1e9);
  5.         maxm=15000;
  6. var     link,head,ke,ts :array[-maxm..maxm] of longint;
  7.         i,j,n,m :longint;
  8.         d       :array[1..maxn] of longint;
  9.         h,p     :array[1..maxn] of longint;
  10.         nh,res  :longint;
  11. procedure add(i,u,v,w:longint);
  12. begin
  13.         link[i]:=head[u];
  14.         head[u]:=i;
  15.         ke[i]:=v;
  16.         ts[i]:=w;
  17. end;
  18. procedure enter;
  19. var     i,u,v,w :longint;
  20. begin
  21.         assign(input,fi);reset(input);
  22.         readln(n,m);
  23.         for i:=1 to m do
  24.                 begin
  25.                         read(u,v,w);
  26.                         add(i,u,v,w);
  27.                         add(-i,v,u,w);
  28.                 end;
  29.         close(input);
  30. end;
  31. procedure swap(var x,y:longint);
  32. var     tg      :longint;
  33. begin
  34.         tg:=x;x:=y;y:=tg;
  35. end;
  36. procedure upheap(i:longint);
  37. var     j:longint;
  38. begin
  39.         j:=i div 2;
  40.         if i>1 then
  41.         if d[h[j]]>d[h[i]] then
  42.                 begin
  43.                         swap(h[i],h[j]);
  44.                         swap(p[h[i]] , p[h[j]] );
  45.                         upheap(j);
  46.                 end;
  47. end;
  48. procedure downheap(i:longint);
  49. var     j :longint;
  50. begin
  51.         j:=i+i;
  52.         if j>nh then exit;
  53.         if (j<nh) and (d[h[j]]>d[h[j+1]]) then inc(j);
  54.         if d[h[i]]>d[h[j]] then
  55.                 begin
  56.                         swap(h[i],h[j]);
  57.                         swap(p[h[i]] , p[h[j]]);
  58.                         downheap(j);
  59.                 end;
  60. end;
  61. function pop:longint;
  62. begin
  63.         pop:=h[1];
  64.         h[1]:=h[nh];
  65.         p[h[1]]:=1;
  66.         dec(nh);
  67.         downheap(1);
  68. end;
  69. procedure push(i:longint);
  70. begin
  71.         inc(nh);
  72.         h[nh]:=i;
  73.         p[i]:=nh;
  74.         upheap(nh);
  75. end;
  76. procedure update(i:longint);
  77. begin
  78.         if p[i]=0 then push(i) else
  79.                 begin
  80.                         upheap(p[i]);
  81.                 end;
  82. end;
  83. procedure process;
  84. var     i,u,v   :longint;
  85. begin
  86.         for i:=1 to n do
  87.                 d[i] := maxc;
  88.         d[1] := 0; push(1);
  89.         repeat
  90.                 u:=pop;
  91.                 res := res + d[u];
  92.                 i:=head[u];
  93.                 while i<>0 do
  94.                         begin
  95.                                 v:=ke[i];
  96.                                 if d[v]>ts[i] then
  97.                                         begin
  98.                                                 d[v]:=ts[i];
  99.                                                 update(v);
  100.                                         end;
  101.                                 i := link[i];
  102.                         end;
  103.         until nh=0;
  104. end;
  105. procedure print;
  106. begin
  107.         assign(output,fo);rewrite(output);
  108.         writeln(res);
  109.         close(output);
  110. end;
  111. begin
  112.         enter;
  113.         process;
  114.         print;
  115. end.
Success #stdin #stdout 0s 4268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/7br6q4
language:
Pascal (fpc 3.0.4)
created:
6 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!