QBSCHOOL - Đến trường
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
fo='';
maxn=5005;
maxc=2000000000;
var n,m:longint;
a,w:array[1..40000] of integer;
d,s,cur,pos:array[1..maxn] of longint;
sl:array[1..maxn] of qword;
free:array[1..maxn] of boolean;
b:array[1..20000,0..3] of longint;
procedure rf;
var i,j,x,y,z,t:longint;
begin
read(n,m);
for i:=1 to m do
begin
for j:=0 to 3 do
read(b[i,j]);
inc(s[b[i,1]]);
if b[i,0]=2 then inc(s[b[i,2]]);
end;
pos[1]:=1; cur[1]:=1;
for i:=2 to n+1 do
begin
pos[i]:=pos[i-1]+s[i-1];
cur[i]:=pos[i];
end;
for i:=1 to m do
begin
a[cur[b[i,1]]]:=b[i,2];
w[cur[b[i,1]]]:=b[i,3];
inc(cur[b[i,1]]);
if b[i,0]=2 then
begin
a[cur[b[i,2]]]:=b[i,1];
w[cur[b[i,2]]]:=b[i,3];
inc(cur[b[i,2]]);
end;
end;
end;
procedure pr;
var i,x,t,min:longint;
begin
for i:=1 to n do
begin
free[i]:=true;
d[i]:=maxc;
end;
d[1]:=0; free[1]:=false; x:=1; sl[1]:=1;
repeat
for i:=pos[x] to pos[x+1]-1 do
if free[a[i]] then
begin
if d[a[i]]=d[x]+w[i] then sl[a[i]]:=sl[a[i]]+sl[x]
else
begin
if d[a[i]]>d[x]+w[i] then
begin
d[a[i]]:=d[x]+w[i];
sl[a[i]]:=sl[x];
end;
end;
end;
min:=maxc-1; t:=0;
for i:=1 to n do
if free[i] and (d[i]<min) then
begin
min:=d[i];
t:=i;
end;
if t=0 then exit;
x:=t; free[x]:=false;
until not free[n];
end;
procedure wf;
begin
writeln(d[n],' ',sl[n]);
end;
begin
assign(input,fi); reset(input);
assign(output,fo); rewrite(output);
rf;
pr;
wf;
close(input); close(output);
end.