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.

Download