记录编号	42837	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	天下第一的吃货殿下	是否通过	通过
代码语言	Pascal	运行时间	0.004 s
提交时间	2012-09-30 20:22:56	内存使用	0.25 MiB

var
 a,b,c,d,e,n,m,qd:longint;
 path,js,long:array[0..100,0..100] of longint;
 gs,min,bs:array[0..100] of longint;
 dl:array[0..2000] of longint;
 jl:array[0..100] of boolean;
       procedure spfa;
        var
            i,j,k,l,now,hd,lt:longint;
                begin
                  for i:=0 to n-1 do
                      min[i]:=maxlongint;
                   min[qd]:=0;
                   path[qd,1]:=qd;
                  hd:=1;
                  lt:=1;
                  dl[1]:=qd;
                  jl[qd]:=true;
                  bs[qd]:=1;
            while lt>=hd do
                  begin
                     now:=dl[hd];
                        for i:=1 to gs[now] do
                            if min[js[now,i]]>min[now]+long[now,js[now,i]]
                               then begin
                                  min[js[now,i]]:=min[now]+long[now,js[now,i]];
                                  path[js[now,i]]:=path[now];
                                  bs[js[now,i]]:=bs[now]+1;
                                  path[js[now,i],bs[js[now,i]]]:=js[now,i];
                                  if jl[js[now,i]]=false then
                                     begin
                                        inc(lt);
                                          if lt=n*2 then lt:=0;
                                        jl[js[now,i]]:=true;
                                        dl[lt]:=js[now,i];
                               end;
                        end;
                     jl[now]:=false;
                   inc(hd);
                     if hd=n*2 then
                   hd:=0;
        end;
end;
 begin
     assign(input,'djs.in');
        reset(input);
         assign(output,'djs.out');
         rewrite(output);
  readln(n,m,qd);
   for a:=1 to m do
       begin
         read(b,c,d);
         inc(gs[b]);
         js[b,gs[b]]:=c;
         long[b,c]:=d;
   end;
 spfa;
   for a:=0 to n-1 do
       begin
         writeln(a,':');
          if (min[a]=0) or (min[a]=maxlongint)
            then writeln('no')
               else begin
                 write('path:');
                  for b:=1 to bs[a] do
                   write(path[a,b],' ');
                 writeln;
                 write('cost:');
                 writeln(min[a]);
          end;
   end;
     close(input);
   close(output);
end.