记录编号	13344	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	0.010 s
提交时间	2009-10-03 17:02:36	内存使用	0.19 MiB

program djs;
var
  path,table:array [0..100,0..100] of longint;
  dij:array [0..100] of longint;
  flag:array [0..100] of boolean;
  min,num,a,b,t,n,m,v,u,i,j:longint;
begin
  fillchar (flag,sizeof(flag),0);
  fillchar (path,sizeof(path),0);
  fillchar (table,sizeof(table),$FF);
  for i:=0 to 100 do dij[i]:=maxlongint;
  assign (input,'djs.in');
  reset (input);
  readln (n,m,v);
  for i:=1 to m do begin
    readln (a,b,t);
    table[a,b]:=t;
  end;
  dij[v]:=0;num:=0;
  close (input);
  assign (output,'djs.out');
  rewrite (output);
  while num<=n do begin
    inc(num);min:=maxlongint;
    for i:=0 to n-1 do if (flag[i]=false) and (dij[i]<min) then begin
      min:=dij[i];
      u:=i;
    end;
    flag[u]:=true;
    for i:=0 to n-1 do if (dij[u]+table[u,i]<dij[i]) and (table[u,i]>0) then begin
      dij[i]:=dij[u]+table[u,i];
      path[i,0]:=path[u,0];
      for j:=1 to path[u,0] do path[i,j]:=path[u,j];
      inc(path[i,0]);
      path[i,path[i,0]]:=i;
    end;
  end;
  for i:=0 to n-1 do begin
    writeln (i,':');
    if path[i,0]=0 then writeln ('no') else begin
      write ('path:',v);
      for j:=1 to path[i,0] do write (' ',path[i,j]);
      writeln;
      writeln ('cost:',dij[i]);
    end;
  end;
  close (output);
end.