记录编号	39021	评测结果	AAAAAAAAAA
题目名称	旅行	最终得分	100
用户昵称	fuhao	是否通过	通过
代码语言	Pascal	运行时间	0.141 s
提交时间	2012-07-03 15:00:24	内存使用	0.22 MiB

const maxn=101; maxk=11;
var
 n,m,k,i,x,y,z,ans,j,kk:longint;
 w:array[0..maxn,0..maxn] of longint;
 u:array[0..maxn] of boolean;
 can:array[0..maxn,0..maxn] of boolean;
 dis:array[0..maxk,-1..maxn] of longint;
 procedure dijkstra;
 var i,j,t,kk:longint;
 begin
  fillchar(dis,sizeof(dis),$7f div 2);
  dis[0,0]:=0;
  for t:=0 to k do
  begin
  fillchar(u,sizeof(u),#0);
  for i:=1 to n do
   begin
    kk:=-1;
    for j:=0 to n-1 do
     if (dis[t,j]<dis[t,kk]) and (not u[j]) then kk:=j;
    if kk=-1 then break;
    u[kk]:=true;
    for j:=0 to n-1 do
     if can[kk,j] and can[j,kk] then
      if dis[t,j]>dis[t,kk]+w[kk,j] then
       dis[t,j]:=dis[t,kk]+w[kk,j] else
     else
      if dis[t+1,j]>dis[t,kk]+2*w[kk,j] then
       dis[t+1,j]:=dis[t,kk]+2*w[kk,j];
   end;
  end;
 end;
begin
 assign(input,'travela.in'); reset(input);
 assign(output,'travela.out'); rewrite(output);
 read(n,m,k);
 while (n<>0) and (m<>0) and (k<>0) do
 begin
 fillchar(w,sizeof(w),$7f div 2);
 fillchar(can,sizeof(can),#0);
 for i:=1 to m do
  begin
   read(x,y,z);
   if w[x,y]>z then w[x,y]:=z;
   can[x,y]:=true;
  end;
 for i:=0 to n-1 do can[i,i]:=true;
 for kk:=0 to n-1 do
  for i:=0 to n-1 do
   for j:=0 to n-1 do
    can[i,j]:=can[i,j] or (can[i,kk] and can[kk,j]);
 dijkstra;
 ans:=dis[0,-1];
 for i:=0 to k do
  if dis[i,n-1]<ans then ans:=dis[i,n-1];
 if ans=dis[0,-1] then writeln(-1) else writeln(ans);
 read(n,m,k);
 end;
 close(input); close(output);
end.