POJ 2394 Checking an Alibi——最短路——Pku 2394
1113 ワード
単一ソース最短のSPFAアルゴリズムでよい.
CODE
CODE
Program Alibi;
Const
maxn=1000;
Var
i,j,k,m,n,f,p,c,o,r,d :Longint;
pre,other,last,dist,data :Array[1..maxn*2]of Longint;
ans,place :Array[1..maxn]of Longint;
Procedure Spfa;
var
seq :Array[1..maxn*10]of Longint;
h,t :Longint;
begin
h:=0;t:=1;seq[1]:=1;
fillchar(dist,sizeof(dist),127);
dist[1]:=0;
while h<t do
begin
inc(h);
i:=seq[h];
j:=last[i];
while j<>0 do
begin
k:=other[j];
if dist[k]>dist[i]+data[j] then
begin
inc(t);seq[t]:=k;
dist[k]:=dist[i]+data[j];
end;
j:=pre[j];
end;
end;
end;
BEGIN
readln(f,p,c,m);
for i:=1 to p do
begin
readln(o,r,d);
inc(k);pre[k]:=last[o];last[o]:=k;other[k]:=r;data[k]:=d;
inc(k);pre[k]:=last[r];last[r]:=k;other[k]:=o;data[k]:=d;
end;
Spfa;
k:=0;
for i:=1 to c do
readln(place[i]);
for i:=1 to c do
if dist[place[i]]<=m then
begin
inc(k);
ans[k]:=i;
end;
writeln(k);
for i:=1 to k do writeln(ans[i]);
END.