记录编号	77816	评测结果	AAAAAAAAAA
题目名称	运输公司	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	Pascal	运行时间	0.021 s
提交时间	2013-11-02 18:25:18	内存使用	0.20 MiB

Program cog605;
    Var
        G:Array[1..20,1..20]Of Longint;
        D:Array[1..20]Of Longint;
        V:Array[1..20]Of Boolean;
        C:Array[1..100,1..100]Of Longint;
        F:Array[0..100]Of Longint;
        A:Array[1..20,1..100]Of Boolean;
        I,J,N,M,K,E,T,L:Longint;
    Procedure Dijkstra(Var A:Longint);
        Var
            I,J,K,P:Longint;
        Begin
            For I:=1 To M Do D[I]:=G[1,I];
            V[1]:=True;
            For I:=2 To M Do
                Begin
                    K:=$3F3F3F3F;
                    For J:=2 To M Do
                        If (Not V[J]) And (D[J]<K) Then
                            Begin
                                K:=D[J];
                                P:=J;
                            End;
                    V[P]:=True;
                    If P=M Then Break;
                    For J:=2 To M Do
                        If (Not V[J]) And (D[J]>K+G[P,J]) Then D[J]:=K+G[P,J];
                End;
            A:=D[M];
        End;
    Begin
        Assign(Input,'transz.in');
        Assign(Output,'transz.out');
        Reset(Input);
        Rewrite(Output);
        Fillchar(G,Sizeof(G),$3F);
        Fillchar(A,Sizeof(A),1);
        Readln(N,M,K,E);
        Repeat
            Readln(I,J,T);
            If G[I,J]>T Then
                Begin
                    G[I,J]:=T;
                    G[J,I]:=T;
                End;
            Dec(E);
        Until E=0;
        Readln(E);
        Repeat
            Readln(T,I,J);
            For L:=I To J Do A[T,L]:=False;
            Dec(E);
        Until E=0;
        For I:=1 To N Do
            For J:=1 To I Do
                Begin
                    Fillchar(V,Sizeof(V),0);
                    For T:=2 To M-1 Do
                        For L:=J To I Do
                            If Not A[T,L] Then
                                Begin
                                    V[T]:=True;
                                    Break;
                                End;
                    Dijkstra(C[J,I]);
                End;
        F[0]:=-K;
        For I:=1 To N Do
            Begin
                T:=Maxlongint;
                For J:=0 To I-1 Do
                    If (C[J+1,I]<>$3F3F3F3F) And (T>F[J]+C[J+1,I]*(I-J)) Then T:=F[J]+C[J+1,I]*(I-J);
                F[I]:=T+K;
            End;
        Writeln(F[N]);
        Close(Input);
        Close(Output);
    End.