VDANGER – spoj

Đề bài: http://vn.spoj.com/problems/VDANGER/

Thuật toán:

• Gợi ý là sử dụng thuật toán Floyd rồi cộng lại ra kết quả bài toán

Code:

VAR
  a :array[1..10000] of byte;
  c :array[1..100,1..100] of longint;
  t :array[1..100,1..100] of byte;
  n :byte;
  m :word;

procedure Enter;
  var i,j :word;
  begin
    readln(n,m);
    for i:=1 to m do readln(a[i]);
    for i:=1 to n do
      begin
        for j:=1 to n do
          begin
            read(c[i,j]); t[i,j]:=j;
          end;
        readln;
      end;
  end;

procedure Optimize;
  var i,j,k :byte;
  begin
    for k:=1 to n do
    for i:=1 to n do
    for j:=1 to n do
    if (c[i,j]>c[i,k]+c[k,j]) then
      begin
        c[i,j]:=c[i,k]+c[k,j];
        t[i,j]:=t[i,k];
      end;
  end;

procedure Quit;
  var
    i :word;
    sum :longint;
  begin
    sum:=0;
    if (a[1]<>1) then sum:=sum+c[1,a[1]];
    for i:=2 to m do sum:=sum+c[a[i-1],a[i]];
    if (a[m]<>n) then sum:=sum+c[a[m],n];
    write(sum);
  end;

BEGIN
  assign(input,''); reset(input);
  assign(output,''); rewrite(output);
  Enter;
  Optimize;
  Quit;
  close(input); close(output);
END.