居然#4#6过不去,似乎没有人出现同样的问题= =

program VijosP1503;

var
n, m, s, i, s0: longint;
pn, v, Count, q: array[1..1000] of longint;
tt: array[1..10000] of boolean;
d: array[1..1000] of int64;
cost: array[1..1000, 1..1000] of longint;
p: array[1..1000, 1..100000] of longint;

procedure init;
var
i, x, y, z: longint;
begin
readln(n, m, s);
s0 := s;
fillchar(pn, sizeof(pn), 0);
for i := 1 to m do
begin
readln(x, y, z);
Inc(pn[x]);
p[x, pn[x]] := y;
cost[x, y] := z;
end;
end;

procedure SPFA;
var
i, j, h, t, x, y: longint;
begin
fillchar(v, sizeof(v), 0);
fillchar(Count, sizeof(Count), 0);
for i := 1 to n do
d[i] := 184467440737095516;
fillchar(q, sizeof(q), 0);
h := 0;
t := 0;
Inc(t);
q[t] := s;
v[s] := 1;
d[s] := 0;
Count[s] := 1;
tt[s]:=true;
while h <> t do
begin
h := (h mod n) + 1;
x := q[h];
v[x] := 0;
for j := 1 to pn[x] do
begin
y := p[x, j];
if d[x] + cost[x, y] < d[y] then
begin
d[y] := d[x] + cost[x, y];
if v[y] = 0 then
begin
t := (t mod n) + 1;
q[t] := y;
v[y] := 1;
Inc(Count[y]);
tt[y]:=true;
if Count[y] > n then
begin
writeln(-1);
//readln;
halt;
end;
end;
end;
end;
end;
end;

begin
init;
SPFA;
fillchar(tt, sizeof(tt), False);
for i := 1 to n do
if not tt[i] then
begin
s := i;
SPFA;
end;
fillchar(tt, sizeof(tt), False);
s := s0;
SPFA;
for i := 1 to n do
begin
if not tt[i] then
writeln('NoPath')
else
writeln(d[i]);
end;
//readln;
end.

2 条评论

  • @ 2015-10-01 21:13:05

    告诉你一个秘密 这道题这样打:
    begin writeln(-1);end.75分
    我记得还有一个题这样打90分
    神奇的数据

  • @ 2015-10-01 21:01:23

    var
    n,m,s,i,j,x,y,z,he,ti:longint;
    a:array[1..1000,1..1000,0..1]of longint;
    b,c,d,e,f:array[1..10000000]of longint;
    procedure spfa(s:longint);
    begin
    fillchar(c,sizeof(c),0);e:=c;
    for i:=1 to n do d[i]:=1000000000;d[s]:=0;
    he:=0;ti:=1;c[1]:=s;
    while he<ti do begin
    inc(he);inc(e[he]);
    for i:=1 to b[c[he]] do begin
    if d[c[he]]+a[c[he],i,1]<d[a[c[he],i,0]] then begin
    if d[a[c[he],i,0]]<0 then begin writeln(-1);halt;end;
    d[a[c[he],i,0]]:=d[c[he]]+a[c[he],i,1];
    inc(ti);c[ti]:=a[c[he],i,0];end;
    end;
    end;
    end;
    begin
    readln(n,m,s);
    for i:=1 to m do begin
    read(x,y,z);inc(b[x]);a[x,b[x],0]:=y;a[x,b[x],1]:=z;end;
    spfa(s);
    for i:=1 to n do if e[i]>n then begin writeln(-1);halt;end;
    f:=d;
    for i:=1 to n do if f[i]=1000000000 then begin spfa(i);
    for j:=1 to n do if e[j]>n then begin writeln(-1);halt;end;break;end;
    spfa(s);
    for i:=1 to n do if d[i]<>1000000000 then writeln(d[i])
    else writeln('NoPath');
    end.
    一年前做的,具体。。spfa
    现在看代码不知道为什么通过17%,ms代码不难
    我的coding方式很有特色,一行不只一句,阅读性低,请海涵
    p.s. 这道题是1053不是1503

    • @ 2015-10-04 00:01:55

      1053。。。再这样粗心NOIP要爆0了。。。
      p.s. Lazarus已经有了一种快捷键CtrlD为代码排版强迫症提供 开头加Program即可

  • 1

信息

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