Cod sursa(job #412077)

Utilizator DanielGGlodeanu Ioan Daniel DanielG Data 5 martie 2010 12:36:23
Problema Algoritmul lui Dijkstra Scor 10
Compilator fpc Status done
Runda Arhiva educationala Marime 1.45 kb
const inf=10000;
var c:array[1..5000,1..5000] of integer;
viz:array[1..5000] of 0..1;
d:array[1..5000] of longint;
tata:array[1..5000] of integer;
f:text;
n,m,min,i,j,k,x,y,cost,x0:longint;
ok:boolean;
procedure citire;
begin
assign(f,'dijkstra.in');reset(f);
read(f,n,m);
for i:=1 to n do
        begin
        for j:=1 to n do
                c[i,j]:=inf;
        c[i,i]:=0;
        end;
for i:=1 to m do
        begin
        read(f,x,y,cost);
        c[x,y]:=cost;
        end;
close(f);
x0:=1;
end;
procedure dijkstra;
begin
for i:=1 to n do
        begin
          d[i]:=c[x0,i];
          tata[i]:=x0;
          viz[i]:=0;
        end;
tata[x0]:=0; viz[x0]:=1; ok:=true;
while ok do
        begin
        min:=inf;
        for i:=1 to n do
           if (viz[i]=0) and (min>d[i]) then
                begin
                  min:=d[i];
                  k:=i;
                end;
        if min<>inf then
                begin
                viz[k]:=1;
                for i:=1 to n do
                        if (viz[i]=0) and (d[i]>d[k]+c[k,i]) then
                                begin
                                  d[i]:=d[k]+c[k,i];
                                  tata[i]:=k;
                                end;
                end
        else ok:=false;
        end;
end;
begin
citire;
dijkstra;
assign(f,'dijkstra.out');rewrite(f);
for i:=2 to n do
        write(f,d[i],' ');
close(f);
end.