Sample input and output

Examples

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

output

16

Violent dfs is enough. We should think about the conditions we have:

1. Planting time of N seeds

2.M existing seeds

3.K hybrid scheme

4. Find the shortest time to plant T

How do I get to dfs?

First of all, the boundary conditions are well set. If it has been planted under the current conditions, we can directly return the time it needs to be planted. Here is period

Then, we now know what to plant, so the parameter we pass in should have the number of the seed to be planted. For this number, we search all the schemes that can plant it, and continue to judge the two seeds obtained by hybridization. If it has not been planted yet, we have to continue to plant until we find one seed number c and the other two seeds a,b has already existed or been planted. At this time, we need to update some structures. For example, the current seed already has a plant.

In addition, we need to find out the minimum planting time, which is obtained by comparing two times: the maximum time for planting a and b and the maximum time for planting a or b, the sum of the two maximum times, and who is smaller in the current period. Therefore, the initial value setting of period should set the existing seed to 0, because it already exists, and then the other initial values should be set larger to take min

#include <bits/stdc++.h>
using namespace std;
const int N=2001;
const int K=100001;
int w[N];//Save the planting time of each seed
int cross[K][3];//Save scheme
int period[N];//Save how soon the corresponding subscript seeds can be hybridized based on the current M seeds
bool plant[N];//Is it planted or existing

int dfs(int t,int k)
{
  if(plant[t]) return period[t];//Avoid repeated requests
  for(int i=1;i<=k;++i)
  {
    if(cross[i][2]==t)
    {
      int a=cross[i][0];
      int b=cross[i][1];
      if(!plant[a]) dfs(a,k);
      if(!plant[b]) dfs(b,k);
      if(plant[a]&&plant[b])
      {
        period[t]=min(period[t],max(w[a],w[b])+max(period[a],period[b]));
      }
    }
  }
  plant[t]=true;
  return period[t];
}


int main()
{
  // Please enter your code here
  int n,m,k,t,tmp;
  scanf("%d%d%d%d",&n,&m,&k,&t);
  memset(period,0x3f3f3f3f,sizeof(period));
  for(int i=1;i<=n;++i) 
    scanf("%d",&w[i]);
  for(int i=1;i<=m;++i)
  {
    scanf("%d",&tmp);
    plant[tmp]=true;
    period[tmp]=0;//There is already this seed. It doesn't take time to get it directly
  }
  for(int i=1;i<=k;++i)
  {
    scanf("%d%d%d",&cross[i][0],&cross[i][1],&cross[i][2]);
  }
  cout<<dfs(t,k);

  return 0;
}

There is also room to optimize the structure and improve the storage method of the scheme: originally, we saved according to the number of schemes. Now we take the hybrid seeds as the subscript, and the two hybrid seeds are stored in a vector as components, so that we don't have to traverse all the scheme numbers during recursion:

#include <bits/stdc++.h>
using namespace std;
const int N=2001;
const int K=100001;
typedef pair<int,int> PII;
vector<PII>cross[N];
int w[N];
// int cross[K][3];
int period[N];
bool plant[N];

int dfs(int t)
{
  if(plant[t]) return period[t];
  for(int i=0;i<cross[t].size();++i)
  {
    int a=cross[t][i].first;
    int b=cross[t][i].second;
    if(!plant[a]) dfs(a);
    if(!plant[b]) dfs(b);
    if(plant[a]&&plant[b])
    {
      period[t]=min(period[t],max(w[a],w[b])+max(period[a],period[b]));
    }
  }
  plant[t]=true;
  return period[t];
}


int main()
{
  // Please enter your code here
  int n,m,k,t,tmp;
  scanf("%d%d%d%d",&n,&m,&k,&t);
  memset(period,0x3f3f3f3f,sizeof(period));
  for(int i=1;i<=n;++i) 
    scanf("%d",&w[i]);
  for(int i=1;i<=m;++i)
  {
    scanf("%d",&tmp);
    plant[tmp]=true;
    period[tmp]=0;//There is already this seed. It doesn't take time to get it directly
  }
  for(int i=1;i<=k;++i)
  {
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    cross[c].push_back({a,b});
  }
  cout<<dfs(t);

  return 0;
}