# 有谁来看看我的spfa有啥问题。。。一直最后一个点-1输出不了。。

``````
Var
n,k,m,s,z,i,t,h,q,j,y,x:longint;
dist,a,state:array[1..10000]of longint;
d,f:array[1..100,1..100]of longint;
wh:array[1..1000,1..100]of boolean;
ch:boolean;

Function pd(dq,x:longint):boolean;
Var
i:longint;
Begin
for i:=1 to k do
if (d[x,i]=1) and (wh[dq,i]) then
exit(false);
exit(true);
End;

Begin
for i:=1 to n-1 do
for i:=1 to k do
begin
for j:=1 to k-1 do
end;
for i:=1 to n do
for j:=1 to n do
f[i,j]:=maxlongint div 2;

for i:=1 to m do
begin
if f[x,y]>z then
begin
f[y,x]:=z;
f[x,y]:=z;
end;
end;

for i:=1 to n do
for j:=1 to n do
if f[i,j]=maxlongint div 2 then
f[i,j]:=0;

for i:=1 to n do
if f[q,i]<>0 then
ch:=true;
if not ch then
begin
writeln(-1);
exit;
end;
for i:=1 to n do
dist[i]:=maxlongint;
dist[s]:=0;
state[1]:=s;
wh[1,a[s]]:=true;
t:=1;
repeat
inc(h);
for i:=1 to n do
if (state[h]<>i) and (f[state[h],i]+dist[state[h]]<dist[i]) and
(pd(h,i)) and (f[state[h],i]<>0) then
begin
inc(t);
state[t]:=i;
dist[i]:=dist[state[h]]+f[state[h],i];
for j:=1 to k do
wh[t,j]:=wh[h,j];
wh[t,a[i]]:=true;
end;
until h>=t;
if dist[q]=maxlongint then
writeln(-1)
else
writeln(dist[q]);
End.

``````

ID
1794

6

2557

606

24%

17