记录编号	97484	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	MID_VAMPIRE	是否通过	通过
代码语言	Pascal	运行时间	0.006 s
提交时间	2014-04-19 11:10:30	内存使用	0.51 MiB

var n,m,s,tot:longint;
    next,head:array[0..10050]of longint;
    e:array[0..10050]of record y,w:longint; end;
    q:array[-100..50000]of longint;
    d,path,a:array[0..500]of longint;
    v:array[0..500]of boolean;
procedure spfa;
var t,h,x,y,i,w:longint;
begin
  filldword(d,sizeof(d)>>2,maxlongint>>2);
  fillchar(v,sizeof(v),0);
  fillchar(q,sizeof(q),0);
  h:=1;t:=1;q[1]:=s;d[s]:=0;v[s]:=true;
  while h<=t do
    begin
      x:=q[h];
      inc(h); v[x]:=false;
      i:=head[x];
      while i<>0 do
        begin
          y:=e[i].y; w:=e[i].w;
          if d[y]>=d[x]+w then
            begin
              d[y]:=d[x]+w;
              path[y]:=x;
              if not v[y] then
                begin
                  v[y]:=true;
                  inc(t);
                  q[t]:=y;
                end;
            end;
          i:=next[i];
        end;
    end;

end;
procedure init;
var i,j,x,y,w,t:longint;
begin
  readln(n,m,s);
  for i:=1 to m do
    begin
      readln(x,y,w);
      inc(tot);
      next[tot]:=head[x];
      head[x]:=tot;
      e[tot].y:=y;
      e[tot].w:=w;
    end;
  spfa;
  for i:=0 to n-1 do
    begin
      writeln(i,':');
      if (d[i]<>maxlongint>>2)and(d[i]<>0) then
        begin
          write('path:',s);
          j:=path[i]; t:=1; a[t]:=i;
          while j<>s do
            begin
              inc(t);
              a[t]:=j;
              j:=path[j];
            end;
          for j:=t downto 1 do write(' ',a[j]);
          writeln;
          writeln('cost:',d[i]);
        end
                            else
                              begin
                                writeln('no');

                              end;
    end;
  //writeln(d[3]);
end;
begin
  assign(input,'djs.in');reset(input);assign(output,'djs.out');rewrite(output);
  init;
  close(input);close(output);
end.