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.