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

var
  i,j,k,n,m,min,ans,l,o,x,y,z,kk:longint;
  a,b:array[0..100,0..100] of longint;
  ok:array[0..100,0..100] of boolean;
  c:array[0..100,0..100] of longint;
  p:array[0..100] of boolean;
  dis:array[0..11,-1..100] of longint;
begin
  assign(input,'travela.in'); reset(input);
  assign(output,'travela.out'); rewrite(output);
  readln(n,m,min);
  while n+m+min<>0 do
    begin
      fillchar(a,sizeof(a),$7F div 4);
      fillchar(ok,sizeof(ok),false);
      for i:=0 to n-1 do a[i,i]:=0;
      for i:=1 to m do
        begin
          readln(x,y,z);
          if a[x,y]>z then
            a[x,y]:=z;
        end;
      b:=a;
      for k:=0 to n-1 do
        for i:=0 to n-1 do
          for j:=0 to n-1 do
            if a[i,k]+a[k,j]<a[i,j] then
              a[i,j]:=a[i,k]+a[k,j];
      for i:=0 to n-1 do
        for j:=i to n-1 do
          if (a[i,j]<100000000)and(a[j,i]<100000000) then
            begin
              ok[i,j]:=true;
              ok[j,i]:=true;
           end;
      fillchar(c,sizeof(c),$7F div 2);
      for i:=0 to n-1 do
        for j:=i to n-1 do
          if ok[i,j]=false then
            begin
              c[i,j]:=b[i,j]*2;
              c[j,i]:=b[j,i]*2;
            end
            else
            begin
              c[i,j]:=b[i,j];
              c[j,i]:=b[j,i];
            end;
      fillchar(dis,sizeof(dis),$7F div 2);
      dis[0,0]:=0;
      for k:=0 to min do
        begin
          fillchar(p,sizeof(p),false);
            for i:=1 to n do
              begin
                kk:=-1;
                for j:=0 to n-1 do
                  if (not p[j]) and (dis[k,j]<dis[k,kk]) then kk:=j;
                if kk=-1 then break;
                p[kk]:=true;
                for j:=0 to n-1 do
                  if ok[kk,j] then
                    begin
                      if dis[k,j]>dis[k,kk]+c[kk,j] then
                        dis[k,j]:=dis[k,kk]+c[kk,j];
                    end
                    else
                    begin
                      if dis[k+1,j]>dis[k,kk]+c[kk,j] then
                        dis[k+1,j]:=dis[k,kk]+c[kk,j]
                    end;
              end;
        end;
      ans:=maxlongint;
      for i:=0 to min do
        if ans>dis[i,n-1] then ans:=dis[i,n-1];
      if ans>100000000 then writeln(-1) else writeln(ans);
      readln(n,m,min);
    end;
  close(input); close(output);
end.