1 hinh dong cuc vui nek ai co may tinh tai pascal ve cop py cai nay veo xem! Wed Jun 20, 2012 8:59 am
Beokaka
Vip
nhà xuất bản: "beokaka";
chú ý: koi được thì tốt không được cháy máy ráng chịu?
chú ý: koi được thì tốt không được cháy máy ráng chịu?
- Code:
PROGRAM ddnt;
CONST
max=100;
maxa=10000;
VAR m,n,s,c:BYTE;
a:ARRAY[0..max,0..max] OF INTEGER;
d:ARRAY[0..max] OF INTEGER;
q:ARRAY[0..max] OF INTEGER;
p:ARRAY[0..max] OF INTEGER;
t:ARRAY[0..max] OF BOOLEAN;
PROCEDURE doctep;
VAR u,v,i:BYTE;
f:TEXT;
BEGIN
assign(f,'dothi.inp');
reset(f);
read(f,m,n,s,c);
{ FOR u:=1 TO n DO
FOR v:=1 TO n DO
IF(u=v)THEN a[u,v]:=0 ELSE a[u,v]:= maxa;}
fillchar(a,sizeof(a),0);
FOR i:=1 TO m DO BEGIN
readln(f,u,v,a[u,v]);
a[v,u]:=a[u,v];
END;
close(f);
END;
PROCEDURE khoitao;
VAR i:INTEGER;
BEGIN
FOR i:=1 TO n DO BEGIN
q[i]:=i;
d[i]:=maxa;
END;
d[s]:=0;
fillchar(t,sizeof(t),TRUE);
END;
{PROCEDURE xoa(u:INTEGER);
VAR k,i:INTEGER;
BEGIN
k:=n;
FOR i:=1 TO k-1 DO BEGIN
q[i]:=q[i+1];
k:=k-1;
END;
END;}
PROCEDURE tinh;
VAR i,u,v,min,c:INTEGER;
BEGIN
REPEAT
u:=0;min:=maxa;
IF t[i] AND (d[i]<min) THEN BEGIN
d[i]:=min;
u:=i;
END;
IF (u=0) OR ( u=c) THEN break;
t[u]:=FALSE;
FOR v:=1 TO n DO
IF (t[v])AND (d[v]>d[u]+a[u,v]) THEN
BEGIN
d[v]:=d[u]+a[u,v];
p[v]:=u;
END;
UNTIL FALSE;
END;
PROCEDURE xuat;
VAR u,j:INTEGER;
BEGIN
IF d[u] = maxa THEN
writeln('khong co duogn di')
ELSE
BEGIN
writeln('duogn di tu',s,' den',c, ':',d[c]);
WHILE s<>c DO
BEGIN
write(u,'<-');
u:=p[u];
END;
writeln(c);
END;
END;
BEGIN
doctep;
khoitao;
tinh;
xuat;
readln;
END.