记录编号	191840	评测结果	AAAAAAAAAA
题目名称	497.奶牛派对	最终得分	100
用户昵称	VacaTionGOD	是否通过	通过
代码语言	Pascal	运行时间	0.196 s
提交时间	2015-10-08 23:19:36	内存使用	7.80 MiB

type aa=array[1..1000,1..1000] of longint;
var
  n,m,x,a,b,t,i,j,k,min,max:longint;
  map1,map2:aa;
  ans:array[1..1000] of longint;
  f:array[1..1000] of boolean;
  d:array[1..1000] of longint;
procedure dijkstra(map:aa);
begin
  for i:=1 to n do
   begin d[i]:=map[x,i]; f[i]:=false; end;
  f[x]:=true;
  for i:=2 to n do
   begin
     min:=maxlongint; k:=0;
     for j:=1 to n do
      if (not f[j]) and (d[j]<min) then
       begin min:=d[j]; k:=j; end;
      if (k=0) or (min=maxlongint) then exit;
     f[k]:=true;
     for j:=1 to n do
      if (not f[j]) and (d[k]+map[k,j]<d[j])
       then d[j]:=d[k]+map[k,j];
   end;
  for i:=1 to n do ans[i]:=ans[i]+d[i];
end;
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 map1[i,j]:=0; map2[i,j]:=0; end
     else begin map1[i,j]:=maxlongint div 2; map2[i,j]:=maxlongint div 2; end;
  for i:=1 to m do
   begin
     readln(a,b,t);
     map1[a,b]:=t;
     map2[b,a]:=t;//if (map[a,b]>t) or (map[a,b]=0) then map[a,b]:=t;
   end;
   dijkstra(map1);
    dijkstra(map2);
   for i:=1 to n do if ans[i]>max then max:=ans[i];
   writeln(max);
end.