fork(4) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/hzQr1z
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!