PWALK - Dạo chơi đồng cỏ

Tác giả: ll931110

Ngôn ngữ: Pascal

Program PWALK;
        Const
                input  = '';
                output = '';
        Var
                                        n,q: integer;
               head,adj,adjcost,trace,x,y,c: array[1..2000] of integer;
                                      fi,fo: text;

Procedure LoadGraph;
          Var
                i: integer;
          Begin
                Assign(fi, input);
                        Reset(fi);

                Fillchar(head, sizeof(head), 0);

                Readln(fi, n, q);
                For i:= 1 to n - 1 do
                        Begin
                                Readln(fi, x[i], y[i], c[i]);
                                inc(head[x[i]]);
                                inc(head[y[i]]);
                        End;

                For i:= 2 to n do head[i]:= head[i] + head[i - 1];

                For i:= 1 to n - 1 do
                        Begin
                                adj[head[x[i]]]:= y[i];
                                        adjcost[head[x[i]]]:= c[i];
                                                        dec(head[x[i]]);

                                adj[head[y[i]]]:= x[i];
                                        adjcost[head[y[i]]]:= c[i];
                                                        dec(head[y[i]]);
                        End;

                head[n + 1]:= 2 * (n - 1);
          End;

Procedure DFS(u: integer);
          Var
                v: integer;
          Begin
                For v:= head[u] + 1 to head[u + 1] do
                        if trace[adj[v]] = 0 then
                                Begin
                                        Trace[adj[v]]:= u;
                                        DFS(adj[v]);
                                End;
          End;

Procedure solve;
          Var
                i,v,s,f: integer;
                    sum: longint;
          Begin
                Assign(fo, output);
                        Rewrite(fo);

                For i:= 1 to q do
                        Begin
                                Fillchar(trace, sizeof(trace), 0);
                                sum:= 0;

                                Readln(fi, s, f);
                                DFS(s);

                                While f <> s do
                                        Begin
                                                For v:= head[f] + 1 to head[f + 1] do
                                                        If adj[v] = trace[f] then
                                                                Begin
                                                                        sum:= sum + adjcost[v];
                                                                        Break;
                                                                End;
                                                f:= trace[f];
                                        End;

                                Writeln(fo, sum);
                        End;

                        Close(fo);
                Close(fi);
          End;

Begin
        LoadGraph;
        solve;
End.

Download