这道题其实还是不难的，只是自己搞混了=-=//晕，做了好久啊，其实就是个spfa，关键是存储路径搞昏了。输出格式要求太严了，航模不能有空格啊，所以因为格式WA了三次，哭啊/(ㄒoㄒ)/~~。贴上代码吧=-=。
const maxn=;
type
link=^node;
node=record
t,v,l:longint;
f:link;
end;
var n,m,s,t,v,l,i,j,toto,sp:longint;
dis:double;
adj:array[..] of link;
bl:array[..,..] of boolean;
f,speed:array[..] of longint;
go:array[..,..,..] of longint;
d:array[..,..] of double;
procedure insert(s,t,v,l:longint);
var p:link;
begin
new(p);
p^.f:=adj[s];
p^.t:=t;
p^.v:=v;
p^.l:=l;
adj[s]:=p;
end;
procedure spfa;
var p:link;
now,l,r,v:longint;
begin
for l:= to do
for r:= to n do d[l,r]:=maxn;
fillchar(bl,sizeof(bl),true);
l:=; r:=; d[,]:=; f[]:=; bl[,]:=false; go[,,]:=; speed[]:=;
while l<=r do
begin
now:=f[l];
v:=speed[l];
p:=adj[now];
while p<>nil do
begin
if p^.v<> then
begin
if d[v,now]+(p^.l/p^.v)<d[p^.v,p^.t] then
begin
d[p^.v,p^.t]:=d[v,now]+(p^.l/p^.v);
go[p^.v,p^.t,]:=now;
go[p^.v,p^.t,]:=v;
if bl[p^.v,p^.t] then
begin
bl[p^.v,p^.t]:=false;
inc(r);
f[r]:=p^.t;
speed[r]:=p^.v;
end;
end;
end
else begin
if d[v,now]+(p^.l/v)<d[v,p^.t] then
begin
d[v,p^.t]:=d[v,now]+(p^.l/v);
go[v,p^.t,]:=now;
go[v,p^.t,]:=v;
if bl[v,p^.t] then
begin
bl[v,p^.t]:=false;
inc(r);
f[r]:=p^.t;
speed[r]:=v;
end;
end;
end;
p:=p^.f;
end;
inc(l);
bl[v,now]:=true;
end;
end;
procedure print(x,v:longint);
begin
if (x<>) then print(go[v,x,],go[v,x,]);
if x<>toto then write(x-,' ')
else write(x-);
end;
begin
readln(n,m,toto);
inc(toto);
for i:= to m do
begin
readln(s,t,v,l);
insert(s+,t+,v,l);
end;
spfa;
dis:=maxn;
for i:= to do
if d[i,toto]<dis then
begin
dis:=d[i,toto];
sp:=i;
end;
print(toto,sp);
end.
(转载请注明出处：http://www.cnblogs.com/Kalenda/)