首先是稀疏图,不难想到dij+heap
观察题目可以知道,0<=k<=10;
所以比较裸的想法就是,d[i,j]表示已经免费了i条线路后到达j的最短路
容易得到
d[i,j]:=min(d[i,j],d[i-1,k]);
d[i,j]:=min(d[i,j],d[i,k]+w[k,j]);
然后在做dij在选择中间点的时候,我们穷举一下免费的线路数就可以了;
然后就要维护10个堆……
语言表述有点渣,具体还是看程序吧
const inf=;
type point=record
num,dis:longint;
end;
node=record
next,cost,point:longint;
end; var edge:array[..] of node;
heap:array[..,..] of point;
d,where:array[..,..] of longint;
h:array[..] of longint;
p:array[..] of longint;
len,x,y,z,i,j,n,m,u,k,s,t:longint; procedure swap(var a,b:point);
var c:point;
begin
c:=a;
a:=b;
b:=c;
end; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y,z:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].cost:=z;
edge[len].next:=p[x];
p[x]:=len;
end; procedure sift(p,i:longint);
var j,x,y:longint;
begin
j:=i shl ;
while j<=h[p] do
begin
if (j+<=h[p]) and (heap[p,j].dis>heap[p,j+].dis) then inc(j);
if heap[p,i].dis>heap[p,j].dis then
begin
x:=heap[p,i].num;
y:=heap[p,j].num;
where[p,x]:=j;
where[p,y]:=i;
swap(heap[p,i],heap[p,j]);
i:=j;
j:=i shl ;
end
else break;
end;
end; procedure up(p,i:longint);
var j,x,y:longint;
begin
j:=i shr ;
while j> do
begin
if heap[p,i].dis<heap[p,j].dis then
begin
x:=heap[p,i].num;
y:=heap[p,j].num;
where[p,x]:=j;
where[p,y]:=i;
swap(heap[p,i],heap[p,j]);
i:=j;
j:=j shr ;
end
else break;
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n,m,k);
readln(s,t);
inc(s); //点序号都+,习惯一点
inc(t);
for i:= to m do
begin
readln(x,y,z);
inc(x);
inc(y);
add(x,y,z);
add(y,x,z);
end;
for i:= to n do
if i<>s then
begin
for j:= to k do
d[j,i]:=inf;
end
else
for j:= to k do
d[j,i]:=;
for i:= to k do
begin
for j:= to n do
begin
heap[i,j].num:=j;
heap[i,j].dis:=d[i,j];
where[i,j]:=j;
end;
h[i]:=n;
end;
for i:= to k do
up(i,s); //起点不一定是0,要初始化堆,一开始这里被坑翻了
for u:= to n do
begin
for j:=k downto do
begin
x:=heap[j,].num;
y:=heap[j,h[j]].num;
if (h[j]=) or (d[j,x]=inf) then continue;
where[j,y]:=; //dij+heap比较重要的细节
swap(heap[j,],heap[j,h[j]]);
dec(h[j]);
sift(j,); //出堆,调整堆
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if (j<>k) and (d[j+,y]>d[j,x]) then //两种情况
begin
d[j+,y]:=d[j,x];
heap[j+,where[j+,y]].dis:=d[j+,y];
up(j+,where[j+,y]);
end;
if (d[j,y]>d[j,x]+edge[i].cost) then
begin
d[j,y]:=d[j,x]+edge[i].cost;
heap[j,where[j,y]].dis:=d[j,y];
up(j,where[j,y]);
end;
i:=edge[i].next;
end;
end;
end;
writeln(d[k,t]); //肯定尽可能免费好啊
end.