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.

Download