记录编号	116678	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	helloworld123	是否通过	通过
代码语言	Pascal	运行时间	0.006 s
提交时间	2014-08-26 16:03:00	内存使用	2.69 MiB

program cogs2;
const
 maxn=100;
var
 i,j,n,m,v,p:longint;
 x,y,max:longint;
 ch:string;
 a:array[0..maxn,0..maxn] of longint;
 f:array[0..maxn] of boolean;
 s:array[0..maxn,0..maxn] of string;
begin
 assign(input,'djs.in'); reset(input);
 assign(output,'djs.out'); rewrite(output);
  readln(n,m,v);
 {for i:=0 to maxn do
  for j:=0 to maxn do
   s[i,j]:='';}
  fillchar(a,sizeof(a),0);
   for i:=1 to m do
   begin
    readln(x,y,a[x,y]);
   end;

  for i:=2 to n do
   begin
    max:=maxlongint;
    for j:=0 to n-1 do
	  if (a[v,j]<max)and(not f[j])and(a[v,j]<>0) then
	   begin
	    max:=a[v,j];
		p:=j;
	   end;
	   f[p]:=true;

	   for j:=0 to n-1 do
	     if (a[v,p]<>0)and(a[p,j]<>0) then
		  if (a[v,j]>a[v,p]+a[p,j]) or ((a[v,j]=0)and(v<>j)) then
		 begin
		  a[v,j]:=a[v,p]+a[p,j];
		  str(p,ch);
		  s[v,j]:=s[v,P]+ch+' ';
		 end;
            end;


	for i:=0 to n-1 do
	 if a[v,i]<>0 then
	  begin
	   writeln(i,':');
	   writeln('path:',v,' ',s[v,i],i);
	   writeln('cost:',a[v,i]);
	  end else
	  begin
	   writeln(i,':');
	   writeln('no');
	  end;
 close(input); close(output);
end.