dijkstra pascal

program dijkstra;
var n,m,s,t,i,j,x,y,w,l,min,p,tt:longint;
    head,d:array[1..1000]of longint;
    open:array[1..1000]of boolean;
    edge:array[1..100000,1..3]of longint;
begin
 read(n,m);
 read(s,t);
 for i:=1 to n do head[i]:=-1;
 for i:=1 to m do
  begin
   read(x,y,w);
   edge[i,1]:=y;
   edge[i,2]:=head[x];
   edge[i,3]:=w;
   head[x]:=i;
  end;
 for i:=1 to n do d[i]:=maxlongint;
 d[s]:=0;
 fillchar(open,sizeof(open),false);
 open[s]:=true;
 for i:=1 to n do
  begin
   min:=maxlongint;
   for j:=1 to n do
    if open[j] then
     if d[j]<min then begin min:=d[j];tt:=j;end;
   p:=head[tt];
   open[tt]:=false;
   while p<>-1 do
    begin
     if min+edge[p,3]<d[edge[p,1]] then
      begin
       d[edge[p,1]]:=min+edge[p,3];
       open[edge[p,1]]:=true;
      end;
     p:=edge[p,2];
    end;
   for j:=1 to n do write(d[j],' ');writeln;
  end;
 for i:=1 to n do write(head[i],' ');
 writeln;
 for i:=1 to n do write(d[i],' ');
end.

좋은 웹페이지 즐겨찾기