fork download
  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
stdin
Standard input is empty
stdout
0