fork download
  1. const fi ='';
  2. fo ='';
  3. maxn =30000+3;
  4. maxc =trunc(1e9)+3;
  5. maxm =trunc(1e5);
  6. type arrd =array[1..maxn] of longint;
  7. arrf =array[1..maxn] of int64;
  8. arrk =array[-maxm..maxm] of longint;
  9. arrh =array[1..maxn] of longint;
  10. var d1,dn,d :arrd;
  11. f1,fn,f :arrf;
  12. n,i,j,m :longint;
  13. res :longint;
  14. ans :arrd;
  15. head :array[1..maxn] of longint;
  16. link,ts,ke :arrk;
  17. // dijkstra heap;
  18. h,p :array[1..maxn] of longint;
  19. nh :longint;
  20. procedure add(i,u,v,w:longint);
  21. begin
  22. link[i]:=head[u];
  23. head[u]:=i;
  24. ke[i]:=v;
  25. ts[i]:=w;
  26. end;
  27. procedure enter;
  28. var u,v,w,k:longint;
  29. begin
  30. assign(input,fi);reset(input);
  31. readln(n,m);
  32. for i:=1 to m do
  33. begin
  34. read(k,u,v,w);
  35. add(i,u,v,w);
  36. if k=2 then add(-i,v,u,w);
  37. end;
  38. close(input);
  39. end;
  40. procedure swap(var x,y:longint);
  41. var tg:longint;
  42. begin
  43. tg:=x;x:=y;y:=tg;
  44. end;
  45. procedure upheap(i:longint);
  46. var j:longint;
  47. begin
  48. j:=i div 2;
  49. if i>1 then
  50. if d[h[i]] < d[h[j]] then
  51. begin
  52. swap(h[i],h[j]);
  53. swap(p[h[i]],p[h[j]]);
  54. upheap(j);
  55. end;
  56. end;
  57. procedure downheap(i:longint);
  58. var j:longint;
  59. begin
  60. j:=i + i;
  61. if j>nh then exit;
  62. if (j<nh) and (d[h[j]] > d[h[j+1]]) then inc(j);
  63. if d[h[j]] < d[h[i]] then
  64. begin
  65. swap(h[i],h[j]);
  66. swap(p[h[i]],p[h[j]]);
  67. downheap(j);
  68. end;
  69. end;
  70. procedure push(i:longint);
  71. begin
  72. inc(nh);
  73. h[nh]:=i;
  74. p[i]:=nh;
  75. upheap(nh);
  76. end;
  77. function pop:longint;
  78. begin
  79. pop:=h[1];
  80. h[1]:=h[nh];
  81. p[h[1]]:=1;
  82. dec(nh);
  83. downheap(1);
  84. end;
  85. procedure update(i:longint);
  86. begin
  87. if p[i]=0 then push(i) else upheap(p[i]);
  88. end;
  89. procedure dijkstra(s:longint);
  90. var u,v,i:longint;
  91. begin
  92. fillchar(h,sizeof(f),0);
  93. fillchar(p,sizeof(p),0);
  94. nh:=0;
  95. fillchar(f,sizeof(f),0);
  96. for i:=1 to n do d[i]:=maxc;
  97. d[s]:=0;
  98. f[s]:=1;
  99. push(s);
  100. repeat
  101. u:=pop;
  102. i:=head[u];
  103. while i<>0 do
  104. begin
  105. v:=ke[i];
  106. if d[v]>d[u]+ts[i] then
  107. begin
  108. d[v]:=d[u]+ts[i];
  109. f[v]:=f[u];
  110. update(v);
  111. end
  112. else
  113. if d[v]=d[u]+ts[i] then
  114. begin
  115. f[v]:=f[u]+f[v];
  116. end;
  117. i:=link[i];
  118. end;
  119. until nh=0;
  120. end;
  121. procedure process;
  122. begin
  123. dijkstra(1);
  124. f1:=f;
  125. d1:=d;
  126. dijkstra(n);
  127. fn:=f;
  128. dn:=d;
  129. for i:=1 to n do
  130. if (d1[i]+dn[i]<>d1[n])
  131. or (f1[i]*fn[i]<>f1[n]) then
  132. begin
  133. inc(res);
  134. ans[res]:=i;
  135. end;
  136. end;
  137. procedure print;
  138. begin
  139. assign(output,fo);rewrite(output);
  140. writeln(d1[n],' ',f1[n]);
  141. close(output);
  142. end;
  143. begin
  144. enter;
  145. process;
  146. print;
  147. end.
Success #stdin #stdout 0s 4204KB
stdin
Standard input is empty
stdout
0 0