蓝桥杯寒假集训第十天（豌豆杂交）
题目描述：
已知有N种豌豆，N种豌豆的成熟时间，两个不同的豌豆A,B能通过杂交产生新的豌豆C，但是杂交也需要时间才能产生C,这个时间被设定成A,B两个的最大成熟时间，假如要得到豌豆G,求出最小的杂交时间
输入描述：
第一行：
N,M,K,T
N表示的是豌豆的所有种数，M表示的是现在已经有的豌豆的种数。K表示能够杂交的组合数，T表示目标的种类型号
第二行：
N个数，代表着从第一个到第N个豌豆成熟所需时间
第三行：
M个数，表示目前已有豌豆种类。
第四行到第K+3行：
表示的k个杂交组合的类型
输出描述：
输出一个数，即输出杂交到目标种类豌豆所耗费的最小时间
样例输入输出：
样例输入:
6 2 4 6
5 3 4 6 4 9
1 2
1 2 3
1 3 4
2 3 5
4 5 6
样例输出：
16
算法思路：
数据结构说明：
dp[i]表示产生i物种所需要的时间。在最开始设定除去最开始的M个杂交时间为0，其他的杂交时间都为无穷大。即除去dp[x3[1],,,,x3[M]]为0，dp[i]均为float('inf')
xi记录第i行的输入数据。i的限制范围为1到3
mix 数组用来存放a,b以及d。d表示由a,b杂交生成d的时间.最开始的mix数组设定为空。
算法说明：
tip:这种数据量大的，涉及搜索的，需要设定多个变量。
key:
- dfs函数关键是找到此点和下一个dfs两个点之间的联系。
- 数组存储元素的技巧
AC代码：
import os
import sys
# 请在此输入您的代码
x1 = list(map(int,input().split()))
x2 = list(map(int,input().split()))
x3 = list(map(int,input().split()))
mix = [[]for i in range(x1[0]+1)]
for i in range(x1[2]):
a,b,c = map(int,input().split())
d = max(x2[a-1],x2[b-1])
mix[c].append([a,b,d])
dp = [float("inf") for i in range(x1[0]+1)]
for i in range(len(x3)):
dp[x3[i]] = 0
def dfs(i):
if dp[i] != float("inf"):
return dp[i]
else:
for j in range(len(mix[i])):
dp[i] = min(dp[i],max(dfs(mix[i][j][0]),dfs(mix[i][j][1]))+mix[i][j][2])
return dp[i]
print(dfs(x1[3]))本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-01-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录