记录编号	21551	评测结果	AAAAAAAAAA
题目名称	奶牛派对	最终得分	100
用户昵称	ZhouZn1	是否通过	通过
代码语言	Pascal	运行时间	0.136 s
提交时间	2010-11-11 15:35:19	内存使用	7.75 MiB

program zzn;
var
        i,j,n,m:longint;
        dist:array[1..2,1..1000]of longint;
        map:array[1..2,1..1000,1..1000]of longint;
        x,a,b,t:longint;
procedure init;
begin
        assign(input,'party.in');
        reset(input);
        assign(output,'party.out');
        rewrite(output);
        readln(n,m,x);
        for i:=1 to n do
         for j:=1 to n do if i<>j then
          begin
             map[1,i,j]:=100000;
             map[2,i,j]:=100000;
          end  else
           begin
              map[1,i,j]:=0;
              map[2,i,j]:=0;
           end;
        for i:=1 to m do
         begin
          readln(a,b,t);
          map[1,a,b]:=t;
          map[2,b,a]:=t;
         end;
        for i:=1 to n do
        if i<>x then
         begin
             dist[1,i]:=map[1,x,i];
             dist[2,i]:=map[2,x,i];
         end;
         dist[1,x]:=0;dist[2,x]:=0;
end;
procedure closef;
begin
        close(input);
        close(output);
end;
procedure djs(k:integer);
var
        v:array[1..1000]of boolean;
        min,p:longint;
begin
        fillchar(v,sizeof(v),0);
        v[x]:=true;
        for i:=1 to n-1 do
         begin
             min:=maxlongint;
             for j:=1 to n do
              begin
                 if (dist[k,j]<min)and(not v[j]) then
                  begin
                      min:=dist[k,j];
                      p:=j;
                  end;
              end;
              v[p]:=true;
              for j:=1 to n do if not(v[j])then
               if dist[k,j]>dist[k,p]+map[k,p,j] then
                dist[k,j]:=dist[k,p]+map[k,p,j];
         end;
end;
procedure main;
var
        ans:longint;
begin
        djs(1);
        djs(2);
        ans:=-maxlongint;
        for i:=1 to n do
         if dist[1,i]+dist[2,i]>ans then ans:=dist[1,i]+dist[2,i];
        writeln(ans);
end;
begin
        init;
        main;
        closef;
end.