QBSCHOOL - Đến trường
Tác giả: ll931110
Ngôn ngữ: Pascal
Program QBSCHOOL2;
Const
input = '';
output = '';
max = 200000000;
Var
u,v,c: array[1..20000] of integer;
k: array[1..20000] of byte;
d: array[1..5000] of longint;
adj,adjcost,h: array[1..40000] of longint;
numway: array[1..5000] of int64;
free: array[1..5000] of boolean;
n,m: integer;
Procedure LoadGraph;
Var
f: text;
i,t: longint;
Begin
Assign(f, input);
Reset(f);
Fillchar(h, sizeof(h), 0);
Readln(f, n, m);
For i:= 1 to m do
Begin
Readln(f, k[i], u[i], v[i], c[i]);
inc(h[u[i]]);
If k[i] = 2 then inc(h[v[i]]);
End;
Close(f);
For i:= 2 to n do h[i]:= h[i] + h[i - 1];
t:= h[n];
For i:= 1 to m do
Begin
adj[h[u[i]]]:= v[i];
adjcost[h[u[i]]]:= c[i];
dec(h[u[i]]);
If k[i] = 2 then
Begin
adj[h[v[i]]]:= u[i];
adjcost[h[v[i]]]:= c[i];
dec(h[v[i]]);
End;
End;
h[n + 1]:= t;
End;
Procedure init;
Var
i: longint;
Begin
Fillchar(free, sizeof(free), true);
For i:= 1 to n do d[i]:= max;
d[1]:= 0;
Fillchar(numway, sizeof(numway), 0);
numway[1]:= 1;
End;
Procedure Dijkstra;
Var
i,u,v,min,iv: longint;
Begin
Repeat
u:= 0;
min:= max;
For i:= 1 to n do
if free[i] and (d[i] < min) then
Begin
u:= i;
min:= d[i];
End;
If u = 0 then break;
free[u]:= false;
For iv:= h[u] + 1 to h[u + 1] do
Begin
v:= adj[iv];
If free[v] then
if d[v] > d[u] + adjcost[iv] then
Begin
d[v]:= d[u] + adjcost[iv];
numway[v]:= numway[u];
End
else if d[v] = d[u] + adjcost[iv] then
numway[v]:= numway[v] + numway[u];
End;
Until false;
End;
Procedure solve;
Var
f: text;
Begin
Assign(f, output);
Rewrite(f);
Writeln(f, d[n], ' ', numway[n]);
Close(f);
End;
Begin
LoadGraph;
init;
Dijkstra;
solve;
End.