记录编号	21522	评测结果	AAAAAAAAAA
题目名称	奶牛派对	最终得分	100
用户昵称	nick09	是否通过	通过
代码语言	Pascal	运行时间	0.213 s
提交时间	2010-11-11 09:49:27	内存使用	3.95 MiB

{用SPFA求出点X到所有点的最短距离和所有点到X的最短距离}
program jfl;
type arr=array[1..1000]of longint;
var i,j,a,b,t,n,m,x,k,max,h:longint;
    g:array[0..1000,0..1000]of longint;
    d1,d2,q:array[0..1000]of longint;
    v:array[0..1000]of boolean;
begin
assign(input,'party.in');
reset(input);
assign(output,'party.out');
rewrite(output);

readln(n,m,x);
filldword(g,sizeof(g)div 4,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,sizeof(d1)shr 2,maxlongint);
fillchar(q,sizeof(q),0);
fillchar(v,sizeof(v),false);
h:=0;
t:=1;
q[t]:=x;
v[x]:=true;
d1[x]:=0;
while h<>t do
begin
    h:=(h mod n)+1;
    k:=q[h];
    v[k]:=false;
    for i:=1 to n do
      if d1[k]+g[k,i]<d1[i] then
      begin
        d1[i]:=d1[k]+g[k,i];
        if not v[i] then
        begin
          t:=(t mod n)+1;
          q[t]:=i;
          v[i]:=true;
        end;
      end;
end;

filldword(d2,sizeof(d2) shr 2,maxlongint);
fillchar(q,sizeof(q),0);
fillchar(v,sizeof(v),false);
h:=0;
t:=1;
q[t]:=x;
v[x]:=true;
d2[x]:=0;
while h<>t do
begin
    h:=(h mod n)+1;
    k:=q[h];
    v[k]:=false;
    for i:=1 to n do
      if d2[k]+g[i,k]<d2[i] then
      begin
        d2[i]:=d2[k]+g[i,k];
        if not v[i] then
        begin
          t:=(t mod n)+1;
          q[t]:=i;
          v[i]:=true;
        end;
      end;
end;

max:=0;
for i:=1 to n do
    if d2[i]+d1[i]>max then
      max:=d2[i]+d1[i];
writeln(max);
close(input);
close(output);
end.