记录编号	21539	评测结果	AAAAAAAAAA
题目名称	497.奶牛派对	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	Pascal	运行时间	0.215 s
提交时间	2010-11-11 11:25:01	内存使用	3.93 MiB

program party;
type arr=array[1..1000] of longint;
var i,a,b,t,n,m,x,k,max:longint;
  G:array[1..1000] of arr;
  D1,D2:arr;
procedure SPFA(var D:arr; flag:boolean);
var Q:arr; v:array[1..1000] of boolean;
  w,h,t,i:longint;
begin
  fillchar(Q,n,0);
  fillchar(v,n,false);
  h:=0; t:=1;
  Q[t]:=x; v[x]:=true; D[x]:=0;
  while h<>t do
  begin
    h:=(h mod n)+1;
    k:=Q[h];
    v[k]:=false;
    for i:=1 to n do
      begin
        if flag then w:=G[k,i] else w:=G[i,k];
        if D[k]+w<D[i] then
        begin
          D[i]:=D[k]+w;
          if not v[i] then
          begin
            t:=(t mod n)+1;
            Q[t]:=i;
            v[i]:=true;
          end;
        end;
      end;
  end;
end;
begin
  assign(input,'party.in'); reset(input);
  assign(output,'party.out'); rewrite(output);
  readln(n,m,x);
  for a:=1 to n do for b:=1 to n do G[a,b]:=MAXINT;
  for i:=1 to m do
  begin
    readln(a,b,t);
    if t<G[a,b] then G[a,b]:=t;
  end;
  filldword(D1,n,maxlongint);
  SPFA(D1,true);
  filldword(D2,n,maxlongint);
  SPFA(D2,false);
  max:=0;
  for i:=1 to n do
    if D1[i]+D2[i]>max then
      max:=D1[i]+D2[i];
  writeln(max);
  close(input); close(output);
end.