The real topic of the 11th provincial competition of Bluebridge cup 2020 - crop hybridization

Title Description

Crop hybridization is an important step in crop cultivation . It is known that there is N Grow crops ( Number 1 to N), The first i The time from sowing to maturity of a crop is Ti. Crops can be crossed in pairs , The hybridization time is the longer of the two .

Such as crops A The planting time is 5 God , crop B The planting time is 7 God , be AB The time taken for hybridization is 7 God . Crop hybridization produces fixed crops , New crops still belong to N One of the crops .

At the beginning , Have one of them M The seeds of a crop ( The number is unlimited , It can support multiple hybridization ). Multiple hybridization processes can be carried out at the same time .

Ask for a given target seed , At least how many days will it take to get .

If it exists 4 Grow crops ABCD, The respective maturity time is 5 God 、7 God 、3 God 、8 God . Initial possession AB The seeds of two crops , Target seed is D, The known hybridization situation is A×B→C,A×C→D.

The shortest hybridization process is ：

The first 1 To the first day 7 God ( crop B Time for ),A×B→C.

The first 8 To the first day 12 God ( crop A Time for ),A×C→D. cost 12 Days get crops D Seeds .

Input

Input the 1 Line inclusion 4 It's an integer N,M,K,T,N Indicates the total number of crop species ( Number 1 to N),M Indicates the number of crop seed types initially owned ,K Indicates the number of hybridization schemes ,T Indicates the number of the target seed . The first 2 Line inclusion N It's an integer , Among them the first i An integer represents the th i The planting time of crops Ti(1≤Ti≤100). The first 3 Line inclusion M It's an integer , Each represents the seed type already owned Kj(1≤Kj≤M),Kj Two are different . The first 4 to K+3 That's ok , Each row contains 3 It's an integer A,B,C, It means the first one A Category crops and category B The third kind of crops can be obtained by hybridization C The seeds of such crops .

Output

Output an integer , Indicates the shortest hybridization time to obtain the target seed .

The sample input

6 2 4 6
5 3 4 6 4 9
1 2
1 2 3
1 3 4
2 3 5
4 5 6

Sample output

16

use python The timeout is a bit serious , But keep a record , Record an idea

import math
N, M, K, T = map(int, input().split())
times = list(map(int, input().split())) #  Crop ripening time 
have = list(map(int, input().split()))  #  Crops already obtained 
ways = []   #  Hybrid program 
for i in range(K):
    ways.append(list(map(int, input().split())))

def dfs(T):
    #  exit 
    if T in have:
        return 0
    #  Target seeds 
    time = math.inf
    for i in ways:
        if i[2] == T:
            tmp = max(times[i[0]-1], times[i[1]-1])
            min_t = max(dfs(i[0]), dfs(i[1])) + tmp
            time = min_t
    return time

print(dfs(T))