记录编号	21455	评测结果	AAAAAAAAAA
题目名称	奶牛派对	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	0.060 s
提交时间	2010-11-10 22:04:40	内存使用	2.43 MiB

{Party
 最短路径
 Author：yangbohua
 Time：2010-11-10}

program party;
type
  bian=record
    v,w,next:longint;
  end;
  he=record
    v,d:longint;
  end;

var
  hpos1,hpos2,list1,list2:array[0..1001] of longint;
  map1,map2:array[0..100001] of bian;
  heap1,heap2:array[0..1001] of he;
  n,m,s,i,j,r1,r2,r3,hl,i1,p,max:longint;

procedure swap1(x,y:longint);
begin
  heap1[0]:=heap1[x];
  heap1[x]:=heap1[y];
  heap1[y]:=heap1[0];
  hpos1[heap1[x].v]:=x;
  hpos1[heap1[y].v]:=y;
end;

procedure swap2(x,y:longint);
begin
  heap2[0]:=heap2[x];
  heap2[x]:=heap2[y];
  heap2[y]:=heap2[0];
  hpos2[heap2[x].v]:=x;
  hpos2[heap2[y].v]:=y;
end;

begin
  assign(input,'party.in');
  reset(input);
  assign(output,'party.out');
  rewrite(output);

  readln(n,m,s);
  fillchar(list1,sizeof(list1),0);
  fillchar(map1,sizeof(map1),0);
  fillchar(list2,sizeof(list2),0);
  fillchar(map2,sizeof(map2),0);
  for i:=1 to m do
  begin
    readln(r1,r2,r3);
    map1[i].v:=r2;
    map1[i].w:=r3;
    map1[i].next:=list1[r1];
    list1[r1]:=i;
    map2[i].v:=r1;
    map2[i].w:=r3;
    map2[i].next:=list2[r2];
    list2[r2]:=i;
  end;

  for i:=1 to n do
  begin
    heap1[i].v:=i;
    heap1[i].d:=maxlongint;
    hpos1[i]:=i;
  end;
  heap1[s].d:=0;
  swap1(1,s);
  hl:=n;
  while hl>0 do
  begin
    i:=heap1[1].v;
    swap1(1,hl);
    hl:=hl-1;
    i1:=2;
    while i1<=hl do
    begin
      if (i1<hl) and (heap1[i1+1].d<heap1[i1].d)
        then inc(i1);
      if heap1[i1].d<heap1[i1 div 2].d then
      begin
        swap1(i1,i1 div 2);
        i1:=i1*2;
      end
      else break
    end;
    p:=list1[i];
    while p>0 do
    begin
      j:=map1[p].v;
      if hpos1[j]<=hl then
        if heap1[hpos1[i]].d+map1[p].w<heap1[hpos1[j]].d then
        begin
          heap1[hpos1[j]].d:=heap1[hpos1[i]].d+map1[p].w;
	  j:=hpos1[j];
          while (j>1) and (heap1[j].d<heap1[j div 2].d) do
          begin
            swap1(j,j div 2);
            j:=j div 2;
          end;
        end;
      p:=map1[p].next;
    end;
  end;

  for i:=1 to n do
  begin
    heap2[i].v:=i;
    heap2[i].d:=maxlongint;
    hpos2[i]:=i;
  end;
  heap2[s].d:=0;
  swap2(1,s);
  hl:=n;
  while hl>0 do
  begin
    i:=heap2[1].v;
    swap2(1,hl);
    hl:=hl-1;
    i1:=2;
    while i1<=hl do
    begin
      if (i1<hl) and (heap2[i1+1].d<heap2[i1].d)
        then inc(i1);
      if heap2[i1].d<heap2[i1 div 2].d then
      begin
        swap2(i1,i1 div 2);
        i1:=i1*2;
      end
      else break
    end;
    p:=list2[i];
    while p>0 do
    begin
      j:=map2[p].v;
      if hpos2[j]<=hl then
        if heap2[hpos2[i]].d+map2[p].w<heap2[hpos2[j]].d then
        begin
          heap2[hpos2[j]].d:=heap2[hpos2[i]].d+map2[p].w;
	  j:=hpos2[j];
          while (j>1) and (heap2[j].d<heap2[j div 2].d) do
          begin
            swap2(j,j div 2);
            j:=j div 2;
          end;
        end;
      p:=map2[p].next;
    end;
  end;

  max:=0;
  for i:=1 to n do
    if heap1[hpos1[i]].d+heap2[hpos2[i]].d>max
      then max:=heap1[hpos1[i]].d+heap2[hpos2[i]].d;

  writeln(max);

  close(input);
  close(output)
end.