Blue Bridge Cup [11th provincial competition] crop hybridization Python 100 points

First, let's analyze the sample , It is assumed that A X B -> C, Now it's time to do it A X C -> D

time Indicates the time required to get the seed in the whole process ( The existing ones are recorded as 0),cost Represents the time required for the seeds to mature

When I first saw this problem, my train of thought was ：time[D] = max([ time[A] + cost[A], time[C] + cost[C] ])

But the result of this idea is ：time[D] = 10, Obviously inconsistent with the meaning of the title

The right way of thinking should be ：time[D] = max([ time[A], time[C] ]) + max([ cost[A], cost[C] ]) = 12

That is to say ： New seeds time = max( Two seeds time) + max( Two seeds cost)

The official website exercise system labels this question as ： graph theory 、 greedy . I built a very complicated AOV network , The code just knocks itself out , To give up . Now it is found that trees are used instead of AOV The Internet is a good choice , Trees and AOV There is no ring like a net

Before reading first 3 Line input

from math import inf
def tran(num):
# Number -> 0 Index started
return int(num) - 1
classes, _, ways, target = map(int, input().split())
target -= 1
cost = list(map(int, input().split()))
# The time required for the seeds to mature
time = [inf] * classes
for idx in map(tran, input().split()):
time[idx] = 0
# It takes time to get the seed 

Then define the tree node , stay __init__ The method is to put cost and time Information entry for

Write a __add__ Method is used to add child nodes

Write a search Method is used to calculate time

class Node:
def __init__(self, cost, time):
self.cost = cost
self.time = time
self.ways = []
def __add__(self, other):
# be used for Pair Add child nodes
self.ways.append(other)
return self
def search(self):
# Used to calculate the seed time
if self.time == inf:
for a, b in self.ways:
waste = max([a.search(), b.search()]) + max([a.cost, b.cost])
# Program time source : Two seeds time The maximum of + Two seeds cost The maximum of
self.time = min([self.time, waste])
return self.time
seed = [Node(cost[idx], time[idx]) for idx in range(classes)]
# Initialize the seed node 

Then after reading N Line input , use + Operators are paired to add child nodes

for idx in range(ways):
a, b, c = map(tran, input().split())
seed[c] += (seed[a], seed[b])
# call Node Class __add__ Method , Add child nodes ( from seed Take... From the list )

Finally target Start searching for the root node , Output the of the root node time Just OK 了

seed[target].search()
print(seed[target].time)

Full marks end