- Easy sssp
- 2013-06-15 10:46:29 @
var
a,b:array[0..1000,0..1000] of longint;
d,dis:array[0..1000] of int64;
sum:array[0..1000] of longint;
f:array[0..1000000] of longint;
c:array[0..1000] of boolean;
n,m,s,i,j,x,y,z:longint;
procedure over;
begin
writeln(-1);
halt;
end;
procedure spfa(o:longint);
var
head,tail,i,j,k:longint;
begin
head:=1; tail:=2;
f[1]:=o;
for i:=1 to n do dis[i]:=maxlongint;
dis[o]:=0;
fillchar(c,sizeof(c),false);
c[o]:=true;
while head<tail do begin
k:=f[head];
for i:=1 to b[k,0] do begin
j:=b[k,i];
if dis[k]+a[k,j]<dis[j] then dis[j]:=dis[k]+a[k,j];
if not c[j] then begin
c[j]:=true;
f[tail]:=j;
inc(tail);
inc(sum[j]);
if sum[j]>n then over;
end;
end;
c[k]:=false;
inc(head);
if dis[o]<0 then over;
end;
if o=s then d:=dis;
end;
begin
readln(n,m,s);
for i:=1 to n do
for j:=1 to n do
if i=j then a[i,j]:=0
else a[i,j]:=maxlongint;
for i:=1 to m do begin
readln(x,y,z);
if (x=y) and (z<0) then over;
if z<a[x,y] then begin
a[x,y]:=z;
inc(b[x,0]);
b[x,b[x,0]]:=y;
end;
end;
spfa(s);
for i:=1 to n do if d[i]=maxlongint then spfa(i);
for i:=1 to n do begin
if i=s then writeln(0)
else if d[i]=maxlongint then writeln('NoPath')
else writeln(d[i]);
end;
end.
5 条评论
-
唐宇奕 LV 7 @ 2013-11-07 20:31:42
有第**七**个点吗?
-
2013-06-19 12:15:38@
终于弄好了,不会见死不救吧~~
var
a,b:array[0..1000,0..1000] of longint;
d,dis:array[0..1000] of int64;
sum:array[0..1000] of longint;
f:array[0..1000000] of longint;
c:array[0..1000] of boolean;
n,m,s,i,j,x,y,z:longint;
procedure over;
begin
writeln(-1);
halt;
end;
procedure spfa(o:longint);
var
head,tail,i,j,k:longint;
begin
head:=1; tail:=2;
f[1]:=o;
for i:=1 to n do dis[i]:=maxlongint;
dis[o]:=0;
fillchar(c,sizeof(c),false);
c[o]:=true;
while head<tail do begin
k:=f[head];
for i:=1 to b[k,0] do begin
j:=b[k,i];
if dis[k]+a[k,j]<dis[j] then dis[j]:=dis[k]+a[k,j];
if not c[j] then begin
c[j]:=true;
f[tail]:=j;
inc(tail);
inc(sum[j]);
if sum[j]>n then over;
end;
end;
c[k]:=false;
inc(head);
if dis[o]<0 then over;
end;
if o=s then d:=dis;
end;
begin
readln(n,m,s);
for i:=1 to n do
for j:=1 to n do
if i=j then a[i,j]:=0
else a[i,j]:=maxlongint;
for i:=1 to m do begin
readln(x,y,z);
if (x=y) and (z<0) then over;
if z<a[x,y] then begin
a[x,y]:=z;
inc(b[x,0]);
b[x,b[x,0]]:=y;
end;
end;
spfa(s);
for i:=1 to n do if d[i]=maxlongint then spfa(i);
for i:=1 to n do begin
if i=s then writeln(0)
else if d[i]=maxlongint then writeln('NoPath')
else writeln(d[i]);
end;
end. -
2013-06-17 12:58:51@
真心弄不了、~
-
2013-06-16 11:41:17@
改了一下格式,look,look
var
a,b:array[0..1000,0..1000] of longint;
d,dis:array[0..1000] of int64;
sum:array[0..1000] of longint;
f:array[0..1000000] of longint;
c:array[0..1000] of boolean;
n,m,s,i,j,x,y,z:longint;
procedure over;
begin
writeln(-1);
halt;
end;
procedure spfa(o:longint);
var
head,tail,i,j,k:longint;
begin
head:=1; tail:=2;
f[1]:=o;
for i:=1 to n do dis[i]:=maxlongint;
dis[o]:=0;
fillchar(c,sizeof(c),false);
c[o]:=true;
while head<tail do begin
k:=f[head];
for i:=1 to b[k,0] do begin
j:=b[k,i];
if dis[k]+a[k,j]<dis[j] then dis[j]:=dis[k]+a[k,j];
if not c[j] then begin
c[j]:=true;
f[tail]:=j;
inc(tail);
inc(sum[j]);
if sum[j]>n then over;
end;
end;
c[k]:=false;
inc(head);
if dis[o]<0 then over;
end;
if o=s then d:=dis;
end;
begin
readln(n,m,s);
for i:=1 to n do
for j:=1 to n do
if i=j then a[i,j]:=0
else a[i,j]:=maxlongint;
for i:=1 to m do begin
readln(x,y,z);
if (x=y) and (z<0) then over;
if z<a[x,y] then begin
a[x,y]:=z;
inc(b[x,0]);
b[x,b[x,0]]:=y;
end;
end;
spfa(s);
for i:=1 to n do if d[i]=maxlongint then spfa(i);
for i:=1 to n do begin
if i=s then writeln(0)
else if d[i]=maxlongint then writeln('NoPath')
else writeln(d[i]);
end;
end. -
2013-06-15 12:36:54@
怎麼都沒代碼塊orz
- 1