QBSCHOOL - Đến trường

Tác giả: RR

Ngôn ngữ: Pascal

{$R-,Q-}
const
  FINP='';
  FOUT='';
  MAXN=20000;
  oo=1000000000;
type
  list=^node;
  node=record u,c:longint; next:list; end;
var
  thuan,nghich:array[1..MAXN] of list;
  d,hpos,h:array[1..MAXN] of longint;
  sl:array[1..MAXN] of int64;
  hsize,n:longint;
procedure add(u,c:longint;var a:list); inline;
var
  p:list;
begin
  new(p); p^.u:=u; p^.c:=c; p^.next:=a; a:=p;
end;
procedure inp; inline;
var
  f:text;
  i,m,u,c,v,l:longint;
begin
  assign(f,FINP); reset(f);
  read(f,n,m);
  for i:=1 to n do
    begin
      thuan[i]:=nil;
      nghich[i]:=nil;
    end;
  for i:=1 to m do
    begin
      read(f,l,u,v,c);
      add(v,c,thuan[u]);
      add(u,c,nghich[v]);
      if l=2 then
        begin
          add(u,c,thuan[v]);
          add(v,c,nghich[u]);
        end;
    end;
  close(f);
end;
procedure swap(var a,b:longint); inline;
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure downHeap(i:longint); inline;
var
  j:longint;
begin
  j:=i shl 1;
  while (j<=hsize) do
    begin
      if (j<hsize) and (d[h[j+1]]<d[h[j]]) then inc(j);
      if d[h[j]]<d[h[i]] then
        begin
          swap(hpos[h[i]],hpos[h[j]]);
          swap(h[i],h[j]);
        end;
      i:=j; j:=i shl 1;
    end;
end;
procedure upHeap(i:longint); inline;
var
  j:longint;
begin
  j:=i shr 1;
  while (i>1) and (d[h[i]]<d[h[j]]) do
    begin
      swap(hpos[h[i]],hpos[h[j]]);
      swap(h[i],h[j]);
      i:=j; j:=i shr 1;
    end;
end;
procedure push(u:longint); inline;
begin
  inc(hsize); h[hsize]:=u; hpos[u]:=hsize;
  upHeap(hsize);
end;
procedure pop(var u:longint); inline;
begin
  u:=h[1]; hpos[u]:=0;
  swap(h[1],h[hsize]);
  hpos[h[1]]:=1; dec(hsize);
  downHeap(1);
end;
procedure dijkstra; inline;
var
  u,v,c:longint;
  p:list;
begin
  for u:=1 to n do d[u]:=oo;
  for u:=1 to n do sl[u]:=-1; sl[1]:=1;
  hsize:=0;
  d[1]:=0; push(1);
  while hsize>0 do
    begin
      pop(u);
      p:=thuan[u];
      while p<>nil do
        begin
          v:=p^.u; c:=p^.c;
          p:=p^.next;
          if d[v]>d[u]+c then
            begin
              d[v]:=d[u]+c;
              if hpos[v]=0 then push(v)
              else upHeap(hpos[v]);
            end;
        end;
    end;
end;
procedure dfs(u:longint); inline;
var
  p:list;
  v,c:longint;
begin
  if sl[u]<>-1 then exit;
  sl[u]:=0;
  p:=nghich[u];
  while p<>nil do
    begin
      v:=p^.u; c:=p^.c;
      p:=p^.next;
      if d[v]+c=d[u] then
        begin
          dfs(v);
          sl[u]:=sl[u]+sl[v];
        end;
    end;
end;
procedure ans; inline;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,d[n],' ',sl[n]);
  close(f);
end;
begin
  inp;
  dijkstra;
  dfs(n);
  ans;
end.

Download