记录编号	74734	评测结果	AAAAAAAAAA
题目名称	奶牛派对	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	Pascal	运行时间	0.074 s
提交时间	2013-10-26 10:30:07	内存使用	7.83 MiB

Program cog497;
    Type
        Graph=Array[0..1000,0..1000]Of Longint;
    Var
        G,Gt:Graph;
        V:Array[0..1000]Of Boolean;
        P,H,D1,D2:Array[0..1000]Of Longint;
        Sz,N,M,I,J,K,X:Longint;
    Procedure Swim(X:Longint; Var D:Array Of Longint);
        Var
            F,S,T:Longint;
        Begin
            T:=H[X];
            S:=X;
            F:=S Shr 1;
            While (F<>0) And (D[H[F]]>D[T]) Do
                Begin
                    P[H[F]]:=S;
                    H[S]:=H[F];
                    S:=F;
                    F:=S Shr 1;
                End;
            P[T]:=S;
            H[S]:=T;
        End;
    Procedure Sink(X:Longint; Var D:Array Of Longint);
        Var
            F,S,T:Longint;
        Begin
            T:=H[X];
            F:=X;
            S:=F Shl 1;
            While S<=Sz Do
                Begin
                    If (S<Sz) And (D[H[S]]>D[H[S+1]]) Then Inc(S);
                    If D[H[S]]>=D[T] Then Break;
                    P[H[S]]:=F;
                    H[F]:=H[S];
                    F:=S;
                    S:=F Shl 1;
                End;
            P[T]:=F;
            H[F]:=T;
        End;
    Procedure Dijkstra(Var G:Graph; Var D:Array Of Longint);
        Var
            I,J,K:Longint;
        Begin
            Fillchar(V,Sizeof(V),0);
            Sz:=0;
            V[X]:=True;
            For I:=1 To N Do D[I]:=G[X,I];
            For I:=1 To N Do
                If I<>X Then
                    Begin
                        Inc(Sz);
                        H[Sz]:=I;
                        P[I]:=Sz;
                        Swim(Sz,D);
                    End;
            For I:=1 To N-1 Do
                Begin
                    J:=H[1];
                    V[J]:=True;
                    H[1]:=H[Sz];
                    Dec(Sz);
                    Sink(1,D);
                    For K:=1 To N Do
                    If (Not V[K]) And (D[K]>D[J]+G[J,K]) Then
                            Begin
                                D[K]:=D[J]+G[J,K];
                                Swim(P[K],D);
                                Sink(P[K],D);
                            End;
                End;
        End;
    Begin
        Assign(Input,'party.in');
        Assign(Output,'party.out');
        Reset(Input);
        Rewrite(Output);
        Readln(N,M,X);
        Fillchar(G,Sizeof(G),$3F);
        Repeat
            Readln(I,J,K);
            If G[I,J]>K Then G[I,J]:=K;
            Dec(M);
        Until M=0;
        Dijkstra(G,D1);
        For I:=1 To N Do
            For J:=1 To N Do
                Gt[I,J]:=G[J,I];
        Dijkstra(Gt,D2);
        J:=0;
        For I:=1 To N Do
            If (I<>X) And (J<D1[I]+D2[I]) Then J:=D1[I]+D2[I];
        Writeln(J);
        Close(Input);
        Close(Output);
    End.