【Easy sssp】第七点怎么过,改了无数次了!

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 条评论

  • @ 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-16 17:12:06

      等寬但還是沒有代碼塊。選中代碼按*Tab*

    • @ 2013-06-16 17:14:59

      好像選中代碼按 Tab 只在发布的时候有显示高亮

    • @ 2013-06-16 17:15:18

      快速入門選段:
      Click here!

  • @ 2013-06-15 12:36:54

    怎麼都沒代碼塊orz

    • @ 2013-06-15 14:09:15

      大家没有好好看快速入门!

  • 1

信息

ID
1053
难度
8
分类
图结构 | 最短路 点击显示
标签
(无)
递交数
7499
已通过
674
通过率
9%
被复制
9
上传者