记录编号	21459	评测结果	AAAAAAAAAA
题目名称	奶牛派对	最终得分	100
用户昵称	belong.zmx	是否通过	通过
代码语言	Pascal	运行时间	0.128 s
提交时间	2010-11-10 22:05:41	内存使用	4.31 MiB

program sparty(input,output);
var
 a:array[1..1000,1..1000]of longint;
 q:array[1..100000]of longint;
 f1,f2:array[1..1000]of longint;
 t:array[0..1000]of boolean;
 n,m,x:longint;
 ans:longint;
 i,j,u,y,o:longint;

procedure spfa1;
var
 i,j:longint;
 head,tail:longint;
begin
 head:=1;
 tail:=1;
 q[head]:=x;
 f1[q[head]]:=0;
 t[q[head]]:=true;
 repeat
  for i:=1 to n do
   if (a[q[head],i]<>maxlongint)and(a[q[head],i]+f1[q[head]]<f1[i]) then
   begin
    if t[i]=false then
    begin
     inc(tail);
     f1[i]:=a[q[head],i]+f1[q[head]];
     t[i]:=true;
     q[tail]:=i;
    end
    else
    begin
     f1[i]:=a[q[head],i]+f1[q[head]];
    end;
   end;
  inc(head);
  t[q[head]]:=false;
 until head>tail;
 for i:=1 to tail do q[i]:=0;
 for i:=1 to n do t[i]:=false;
end;

procedure spfa2;
var
 i,j:longint;
 head,tail:longint;
begin
 head:=1;
 tail:=1;
 q[head]:=x;
 f2[q[head]]:=0;
 t[q[head]]:=true;
 repeat
  for i:=1 to n do
   if (a[i,q[head]]<>maxlongint)and(a[i,q[head]]+f2[q[head]]<f2[i]) then
   begin
    if t[i]=false then
    begin
     inc(tail);
     f2[i]:=a[i,q[head]]+f2[q[head]];
     t[i]:=true;
     q[tail]:=i;
    end
    else
    begin
     f2[i]:=a[i,q[head]]+f2[q[head]];
    end;
   end;
  inc(head);
  t[q[head]]:=false;
 until head>tail;
end;

begin
 assign(input,'party.in');
 reset(input);
 readln(n,m,x);
 for i:=1 to n do
  for j:=1 to n do a[i,j]:=maxlongint;
 for i:=1 to m do
 begin
  readln(u,y,o);
  a[u,y]:=o;
 end;
 close(input);

 for i:=1 to n do
 begin
  f1[i]:=maxlongint;
  f2[i]:=maxlongint;
 end;

 spfa1;
 spfa2;

 for i:=1 to n do
  if f1[i]+f2[i]>ans then ans:=f1[i]+f2[i];

 assign(output,'party.out');
 rewrite(output);
 writeln(ans);
 close(output);
end.