记录编号	75474	评测结果	AAAAAAAAAT
题目名称	[NOIP 2012]文化之旅	最终得分	90
用户昵称	Ezoi_XY	是否通过	未通过
代码语言	Pascal	运行时间	1.020 s
提交时间	2013-10-27 21:35:57	内存使用	0.27 MiB

Program cog1271;
    Var
       G,D:Array[1..110,1..110]Of Longint;
       P:Array[1..110,1..110]Of Boolean;
       C:Array[1..110]Of Longint;
       E:Array[1..110]Of Boolean;
       N,K,M,S,T,I,J,L,A:Longint;
    Procedure Dfs(X,U:Longint);
        Var
            I,J:Longint;
            Et:Array[1..110]Of Boolean;
        Begin
            If X=S Then
                Begin
                    A:=U;
                    Exit;
                End;
            For I:=1 To K Do Et[I]:=E[I];
            For I:=1 To N Do
                If (G[X,I]<>$3F3F3F3F) And (E[C[I]]) And ((I=S) Or (C[I]<>C[S]) And (Not P[C[I],C[S]])) And (U+G[X,I]+D[I,S]<A) Then
                    Begin
                        For J:=1 To K Do
                            If P[C[I],J] Then E[J]:=False;
                        E[C[I]]:=False;
                        Dfs(I,U+G[X,I]);
                        For J:=1 To K Do E[J]:=Et[J];
                    End;
        End;
    Begin
        Assign(Input,'culture.in');
        Assign(Output,'culture.out');
        Reset(Input);
        Rewrite(Output);
        Fillchar(G,Sizeof(G),$3F);
        A:=Maxlongint;
        Readln(N,K,M,T,S);
        For I:=1 To N Do Read(C[I]);
        For I:=1 To K Do
            For J:=1 To K Do
                Begin
                    Read(L);
                    If L=0
                        Then P[J,I]:=False
                        Else P[J,I]:=True;
                End;
        Repeat
            Readln(I,J,L);
            If G[I,J]>L Then
                Begin
                    G[I,J]:=L;
                    G[J,I]:=L;
                End;
            Dec(M);
        Until M=0;
        D:=G;
        For I:=1 To N Do
            For J:=1 To N Do
                For L:=1 To N Do
                    If D[J,L]>D[J,I]+D[I,L] Then D[J,L]:=D[J,I]+D[I,L];
        For I:=1 To K Do E[I]:=Not P[C[T],I];
        E[C[T]]:=False;
        Dfs(T,0);
        If A=Maxlongint
            Then Writeln('-1')
            Else Writeln(A);
        Close(Input);
        Close(Output);
    End.