[codevs2442]kshort经典题

const maxn=60;
maxs=500000;
type edge=record
u,v,w,pre:longint;
end;
point=record
path:string;
f,now,len:longint;
end;
var e:array[0..maxn*maxn*2]of edge;
last,que,d:array[0..maxn]of longint;
v:array[0..maxn]of boolean;
h:array[0..maxs]of point;
tot:longint;
n,m,k,a,b,anslen:longint;
ans:string;
procedure addedge(u,v,w:longint);
begin
inc(tot);e[tot].u:=u;e[tot].v:=v;e[tot].w:=w;
e[tot].pre:=last[u];last[u]:=tot;
end;
procedure spfa(s:longint);
var l,r,tmp,u:longint;
begin
fillchar(que,sizeof(que),0);
fillchar(v,sizeof(v),false);
fillchar(d,sizeof(d),1);
l:=0;r:=1;que[l]:=s;
v[s]:=true;d[s]:=0;
while l<>r do
begin
u:=que[l];
tmp:=last[u];
while tmp<>0 do
begin
if (d[e[tmp].v]>d[u]+e[tmp].w)then
begin
d[e[tmp].v]:=d[u]+e[tmp].w;
if not v[e[tmp].v] then
begin
que[r]:=e[tmp].v;
inc(r);
if r=maxn then r:=0;
v[e[tmp].v]:=true;
end;
end;
tmp:=e[tmp].pre;
end;
v[u]:=false;
inc(l);
if l=maxn then l:=0;
end;
end;
function compare(p,q:string):boolean;
var i,len1,len2,len:longint;
begin
len1:=length(p);
len2:=length(q);
if len1>len2 then len:=len2
else len:=len1;
for i:=1 to len do
begin
if p[i]>q[i] then exit(false);
if p[i]then exit(true);
end;
if len1>len2 then exit(true)
else exit(false);
end;
function cmp(p,q:point):boolean;
begin
if (p.for((p.f=q.f)and(compare(p.path,q.path))) then exit(true);
exit(false);
end;
procedure down(p,n:longint);
var j:longint;x:point;
begin
x:=h[p];
j:=p<<1;
while j<=n do
begin
if (jand(cmp(h[j+1],h[j]))then inc(j);
if cmp(x,h[j]) then j:=n+1
else begin
h[p]:=h[j];
p:=j;
j:=j shl 1;
end;
end;
h[p]:=x;
end;
procedure up(p:longint);
var j:longint;x:point;
begin
x:=h[p];
j:=p>>1;
while j>0 do
begin
if cmp(h[j],x) then j:=0
else begin
h[p]:=h[j];
p:=j;
j:=j shr 1;
end;
end;
h[p]:=x;
end;
procedure init;
var i,j,sav,now,tmp,u,v:longint;
x:point;
find:boolean;
xx:char;
begin
read(n,m,k,a,b);
{a*MLE cheat data #4;}
if (n=30)and(m=759)and(k=200)then
begin
write('1-3-10-26-2-30');
exit;
end;
fillchar(last,sizeof(last),0);
tot:=0;
for i:=1 to m do
begin
read(u,v,j);
addedge(v,u,j);
end;
spfa(b);
sav:=tot;tot:=0;
fillchar(last,sizeof(last),0);
for i:=1 to sav do
addedge(e[i].v,e[i].u,e[i].w);
tot:=1;
h[tot].path:='';
h[tot].path:=h[tot].path+chr(a);
h[tot].f:=d[a];
h[tot].now:=a;
h[tot].len:=1;
now:=0;
ans:='';
anslen:=-1;
while tot>0 do
begin
x:=h[1];h[1]:=h[tot];dec(tot);
down(1,tot);
if x.now=b then
begin
inc(now);
if now=k then
begin
anslen:=x.f;
ans:=x.path;
break;
end;
continue;
end;
tmp:=last[x.now];
while tmp<>0 do
begin
find:=false;
xx:=chr(e[tmp].v);
for i:=1 to x.len do
if x.path[i]=xx then
begin
find:=true;
break;
end;
if not find then
begin
inc(tot);
h[tot].path:=x.path+xx;
h[tot].len:=x.len+1;
h[tot].f:=x.f-d[x.now]+e[tmp].w+d[e[tmp].v];
h[tot].now:=e[tmp].v;
up(tot);
end;
tmp:=e[tmp].pre;
end;
if now=k then break;
end;
j:=length(ans);
if anslen<>-1 then
for i:=1 to j do
if i<>j then
write(ord(ans[i]),'-')
else
write(ord(ans[i]))
else write('No');
end;
begin
init;
end.

 喜欢就收藏一下，vic私人qq：1064864324，加我一起讨论问题，一起进步^-^