Problem statement 2D, who is good at cooking, is trying to make lunch. Cooking requires…
- User
Problem statement
2D, who is good at cooking, is trying to make lunch. Cooking requires all N ingredients a_ {0}, a_ {1},…, a_ {N−1}.
Now, 2D's refrigerator doesn't contain any ingredients, so I have to go to the supermarket to buy it. At the supermarket, you can buy the material a_ {i} for the price x_ {i} yen.
2D is also a wizard and can use M types of magic. The i-th magic can be changed to the material t_ {i} by applying it to the material s_ {i}, and conversely to s_ {i} by applying it to the material t_ {i}. In addition, you can repeatedly use multiple spells on a single material. For example, you can get r from p using the magic of changing from p to q and the magic of changing from q to r.
2D decided to use the power of magic to prepare the materials as cheaply as possible. Find the minimum sum of the prices of the ingredients that 2D needs to buy to complete the dish. input
The input is given in the following format.
N a_ {0} x_ {0} ... a_ {N−1} x_ {N−1} M s_ {0} t_ {0} ... s_ {M−1} t_ {M−1}
Constraint
- All numbers are integers
- All material names consist of at least 1 and no more than 10 lowercase letters.
- If i ≠ j, then a_ {i} ≠ a_ {j}
- 1 \ ≤ x_ {i} \ ≤ 1,000
- 1 \ ≤ N \ ≤ 5,000
- 0 \ ≤ M \ ≤ {\ rm min} (N (N−1) / 2, 1000)
- s_ {i} ≠ t_ {i}
- There is no duplication in the pair of s_ {i}, t_ {i}
- s_ {i}, t_ {i} are included in a_ {0},…, a_ {N−1}
output
Print the answer in one line.
sample
Sample input 1
2 tako 2 yaki 1 1 tako yaki
You can magically turn a cheap yaki into a tako, so buy two yaki.
Sample output 1
2
Sample input 2
Five a 1 b 2 c 2 d 4 e 3 Five b a a c c d e b c b
Sample output 2
Five
As shown below, all materials can be changed from a.
- a: a as it is
- b: a-> c-> b
- c: a-> c
- d: a-> c-> d
- e: a-> b-> e
Example
Input
2 tako 2 yaki 1 1 tako yaki
Output
2
Assistant
We need to find minimum sum of prices of ingredients to buy such that we can obtain all N distinct ingredients (a_i) via magical conversions. We have a set of ingredients (names), each with a price to buy. There are M undirected (bidirectional) magical connections: each magic allows transformation between s_i and t_i in either direction (so it's essentially an undirected edge between two ingredients). Because transformations can be applied repeatedly, any ingredient can be transformed into any other ingredient within the same connected component (graph of ingredients with edges from magic). Actually, since magic is bidirectional and can be used repeatedly, the transformation relation is an equivalence relation: ingredients are partitioned into connected components. Within a component, you can transform any ingredient to any other. Therefore, for each component, you need to have at least one ingredient purchased, and then you can transform that purchased ingredient into all other ingredients in that component. However, you need to have each of the N ingredients present: you could either buy it directly, or obtain it via transformation from some bought ingredient. Since transformations are free (no cost beyond buying the initial ingredient), the problem reduces to: Given a graph with N vertices (ingredients), each vertex has a cost (price). We need to select a set of vertices such that every vertex is either selected or reachable from some selected vertex (i.e., a dominating set? Actually, not dominating: transformation allows to replace one ingredient with another, meaning if we have one ingredient in a component, we can transform it into any other ingredient in that component. So we need to cover all vertices by selecting at least one vertex from each connected component. Because within a component, if we have any one vertex, we can produce all others via transformations. So the objective: For each connected component, we must buy at least one ingredient from that component. To minimize total cost, we simply pick the cheapest ingredient in each component. Then total minimum sum = sum over components of min cost in that component.
That seems straightforward. But careful: The graph is undirected and components are defined by the magic edges. However, the constraints: M ≤ min(N(N-1)/2, 1000). So up to 5000 vertices, but M up to 1000 edges. So graph is sparse.
Thus answer is sum of minimum price in each connected component.
Let's check sample1: Ingredients: tako price2, yaki price1. Magic: tako yaki. So they are in same component. Minimum price =1. Need to buy at least 1 ingredient, so total cost=1? But sample output is 2. Wait sample says: "you can magically turn a cheap yaki into a tako, so buy two yaki." Actually, there are 2 ingredients total. If you buy one yaki, you can transform that yaki into tako? With the magic, you can turn yaki into tako. But then you only have one ingredient: if you transform the yaki into tako, you lose the yaki; you need both tako and yaki simultaneously for the dish. Since you need to have all N ingredients at the same time, you cannot use the same purchased item to be transformed into multiple ingredients because that would require having multiple copies? Indeed, you need to "prepare the materials" meaning you need to have each of the N ingredients available. If you buy one yaki, you could transform it into a tako, but then you would have tako but not yaki. You could also keep it as yaki. You need both simultaneously. So you need to have at least one instance of each ingredient. Transformations can convert a purchased ingredient into another, but you can't duplicate an ingredient. So if you have one purchased item, you can only get one ingredient at a time. To get both, you need to purchase at least two items. However, you could purchase two yakis, then transform one into tako, ending with one yaki and one tako. So total cost = 2*yaki_price =2. That matches sample output. So the earlier reasoning about picking one per component is insufficient. You need to obtain all N distinct ingredients. Since each purchased ingredient can be transformed into exactly one ingredient (the final one you need), you need at least N purchased items? But you can also buy multiple of the same ingredient. The key: you need to end up with N ingredients (the set). You can purchase any number of each ingredient (paying its price per unit). Magic can transform one unit of an ingredient into one unit of another ingredient within the same component (since magic works on a material). So effectively, each purchased unit can be transformed arbitrarily along the graph to become any ingredient in the same component, but each unit yields exactly one unit of some ingredient. Since you need one unit of each distinct ingredient (presumably exactly one of each), you need at least N units total. But you might purchase multiple units of cheap ingredients and then transform them into the needed ones. However, there is no cost to transformation, and you can apply multiple spells repeatedly on a single material. So the problem reduces to: we have a set of ingredients (nodes) with costs. We need to obtain exactly one unit of each node. We can purchase any number of units of any nodes. For each purchased unit, we can apply transformations (free) to change it into any node reachable from its original node in the graph (the transformation graph). So effectively, after purchasing, we can assign each purchased unit to become some node in its connected component. We need to cover all nodes at least once (we need one unit per node). The goal is to minimize total purchase cost, given that each purchased unit costs the price of the node we buy (not the transformed node). So we can think: for each connected component, we need to produce all nodes in that component. Since transformations only work within the component, we must purchase some number of units from nodes in that component, and then assign each unit to become a distinct node of the component (we need to cover all nodes). Because we can purchase from any node within the component, and then transform to any other node within the component. So the problem for each component is: given a set of nodes with costs, we need to acquire at least one unit of each node. We can buy multiple copies of the same node. Each bought unit can be transformed to any node, but each node must be covered by at least one unit. The objective is to minimize sum of costs of purchased units. Since there is no penalty for extra units (we could purchase more than needed, but that would increase cost, so we wouldn't), we will buy exactly the number of nodes in the component, one unit per required distinct node. But we can choose which nodes to buy: we could buy all nodes directly, costing sum of all costs. Or we could buy multiple copies of a cheap node and transform them to the others. For example, in a component with k nodes, we could buy k copies of the cheapest node, each costing min_cost, then transform each copy into a different node, total cost = k * min_cost. Alternatively, we could buy a mix: maybe buy some cheap and some expensive if there are constraints? But since any purchased node can be transformed to any other node, there's no restriction: if you buy from node A, you can transform it to B. So the only thing that matters is the cost of the node you purchase from. So for each unit you need to produce, you can purchase it from the cheapest node in the component. Because you could buy all units from that cheapest node, then transform each to a distinct required node. That yields total cost = (number of nodes in component) * (minimum cost in component). Is there any reason you couldn't transform multiple copies from the same cheap node into different nodes? The magic is applied to each material individually. There's no limit: you can apply the sequence of spells to each copy independently. So yes.
Thus overall total minimum cost = sum over components of (size_of_component * min_cost_in_component).
Check sample1: component size = 2, min_cost = 1, sum = 2 -> matches.
Sample2: Let's compute. Ingredients: a(1), b(2), c(2), d(4), e(3). Magic edges: b-a, a-c, c-d, e-b, c-b. So graph: nodes a,b,c,d,e all connected? Let's see edges: b-a connects b and a. a-c connects a and c. c-d connects c and d. e-b connects e and b. c-b connects c and b. So it's one connected component of size 5. Minimum cost is min(1,2,2,4,3)=1. So total cost = 5*1 =5. Sample output 5 matches.
Thus answer is simply that. So problem reduces to finding connected components in an undirected graph of up to 5000 nodes and 1000 edges. Compute for each component: number of nodes, minimum price. Sum of size * min.
But wait: is there any nuance about the names? We have ingredient names as strings. But constraints ensure that all s_i, t_i are in the list of a_i. So we can map each name to an index (0..N-1). Then build adjacency list. Then do DFS/BFS to find components.
Time complexity: O(N + M) with mapping via hashmap/dictionary.
Edge cases: M=0, then each ingredient is its own component. For each ingredient, size=1, min = its price, sum = sum of all prices. But is that correct? If there is no magic, you cannot transform, so you must buy each ingredient directly. So total cost = sum of all prices. Indeed size=1 per component, so sum = sum of prices, matches.
Potential twist: Could there be a situation where you need to consider that you might buy some ingredient outside the component? No, because transformations only within component. But you could purchase an ingredient from a different component and then try to transform it into an ingredient in the desired component? No, because magic only works between ingredients that are directly connected, and connectivity is limited to within component. So you cannot transform across components. So each component's ingredients must be satisfied using purchases from within that component.
Thus solution is straightforward.
But wait, there is also the possibility that you could buy an ingredient from one component and use it to produce multiple ingredients in the same component via duplication? But duplication is not allowed; each purchased unit yields one final unit. So if component size is k, you need at least k purchased units, all from within that component (or could some be from other components? No, because transformation across components impossible). So you need at least k purchases. The cheapest per unit cost within component is min_cost. So minimum total cost for component is at least k * min_cost. And this is achievable by buying k copies of the cheapest node. So it's optimal.
Thus answer = sum_{component} (component_size * min_price_in_component).
Implement:
Read N. For i in range(N): read name, price. Store: assign index i, store price[i] and map name->i. Read M. For each of M: read s, t. Get indices, add edge to adjacency list (undirected). Then visited = [False]*N. total = 0 for each node not visited: BFS/DFS to collect nodes in component. compute size = count, min_price = min(price[node] for node in component) total += size * min_price print(total)
Memory: adjacency list of size N, each with list. M up to 1000, fine.
Potential pitfalls: Input lines may have extra spaces? Use split.
N up to 5000, fine.
Now test with given samples.
Also test with simple: N=1, no magic. Then total = 1*price = price.
Another test: N=3, prices: a1=5, a2=6, a3=7, magic: a1-a2, so components: {a1,a2} size2 min5 => cost10, plus {a3} size1 min7 => cost7, total17. But maybe you could buy a1 twice (cost10) to get a1 and a2, and buy a3 (7) total17. Yes.
But could there be a scenario where buying a mixture yields less than k*min? Suppose we have component of 2 nodes A cost 10, B cost 1. Minimum =1, size2 => cost2. But if you buy B twice (cost2), you get B and transform one to A, total cost2. Cheaper than buying A and B separately (11). So yes.
Edge case: component with size=0? Not possible.
Thus solution is correct.
But wait: Problem statement says: "2D decided to use the power of magic to prepare the materials as cheaply as possible. Find the minimum sum of the prices of the ingredients that 2D needs to buy to complete the dish." And "you can repeatedly use multiple spells on a single material." So transformation is free.
Thus answer is sum over components of size * min cost.
Thus I'll implement.
Implementation details:
Since ingredient names are up to 10 lowercase letters, we can use dictionary (python dict) to map names to indices.
Read N as integer. Then loop N times: read line, split into name and price (int). assign index i, store price[i] = price, name_to_idx[name] = i. Read M as integer. Initialize adjacency list: adj = [[] for _ in range(N)] Loop M times: read line, split into s, t. i = name_to_idx[s], j = name_to_idx[t]. adj[i].append(j); adj[j].append(i).
Then visited = [False]*N total = 0 for i in range(N): if not visited[i]: # BFS queue = [i] visited[i] = True comp_nodes = [i] while queue: u = queue.pop(0) # O(n) pop from list? better use collections.deque But N up to 5000, fine. However, I'll use deque for efficiency. Actually, I'll use list as stack for DFS to simplify: stack = [i] visited[i] = True comp_nodes = [] while stack: u = stack.pop() comp_nodes.append(u) for v in adj[u]: if not visited[v]: visited[v] = True stack.append(v) After collecting, size = len(comp_nodes) min_price = min(prices[u] for u in comp_nodes) total += size * min_price
Print total.
Time O(N+M). Works.
Now, check constraints: M ≤ 1000 but N up to 5000, so adjacency list fine.
Potential oversight: The graph might have loops? No, s_i != t_i. No duplication of pairs, but might be multiple edges? No duplication ensures no parallel edges, but could there be indirect connections? Not an issue.
Thus answer.
But let me double-check the interpretation: The problem says "you can repeatedly use multiple spells on a single material." That implies you can transform one material into another. But do you need to have all materials at the same time? Yes, the dish requires all ingredients. So you need to possess each ingredient. Starting from bought items, you can apply spells to change them. After transformations, you'll have some set of ingredients. The goal is to have all N distinct ingredients.
Thus each purchased item can become at most one final ingredient. So we need at least N items purchased. However, if some ingredient is cheap, we can buy many copies of it and transform each to a needed ingredient. So indeed we need at least number of ingredients in each component copies from that component. But what if a component's size is >1, could we possibly get away with fewer than size purchases by using some purchased item from another component that can be transformed? No, because you cannot transform across components. So must purchase at least size items from that component. And the cheapest per item cost in the component is min_price. So lower bound is size*min_price. Achievable as described. So answer.
Now verify with a more complex scenario: Suppose component has nodes with different costs, but there is a twist: you cannot transform a cheap node into all others if there is a node that is not reachable? But by definition of component, it's reachable. So fine.
Thus solution is correct.
Now coding.
Edge Cases: M=0 -> each node isolated, component sizes=1, total = sum(prices). Works.
Large N: up to 5000, BFS/DFS recursion may exceed recursion limit if using recursion, so iterative DFS is safe.
Now produce final answer.
I'll also note that there is no constraint that N <= 5000 but M <= 1000, so number of edges limited.
Thus implementation done.
But let's ensure reading input correctly: Input format: N a0 x0 ... a_{N-1} x_{N-1} M s0 t0 ... s_{M-1} t_{M-1}
All lines contain strings and ints. Use input().split().
Now, sample 2 has "Five" but that's a placeholder? Actually sample input 2 shows "Five" but that likely means "5". Let's ignore.
Now, possible pitfalls: There might be trailing spaces. Not an issue.
Now answer.
But wait, there is a nuance: The transformation is reversible and can be used repeatedly. However, does the transformation consume the original ingredient? Typically, you apply a spell to a material to change it into another. So you have one material, you cast a spell, it becomes another. So you lose the original. That's fine: you can start with a yaki, cast spell to become tako. So that works.
Now think about whether you need to have the ingredient present to apply the spell? Yes, you apply it to an ingredient you already have. So to transform, you need to have that ingredient. So if you buy two yaki, you can keep one as yaki and transform the other to tako. That yields both.
Now consider scenario: You have a component with 3 nodes: A cheap, B medium, C expensive. You could buy 3 of A and transform to A, B, C. So cost = 3cost_A. But could you do better by buying 2 of A and 1 of B? That would be 2cost_A + cost_B. Since cost_B > cost_A, that's higher. So not better. So indeed min is size*min_cost.
Now, is there any scenario where you need to consider that you cannot transform multiple copies from the same node because maybe you need to apply spells in sequence that require intermediate materials? But you can apply spells on each copy independently. No resource constraints.
Thus solution stands.
Now implement.
After coding, test with sample1:
Input: 2 tako 2 yaki 1 1 tako yaki
Map: tako idx0 price2, yaki idx1 price1. Edge: 0-1. Component includes both: size=2 min=1 => total=2. Print 2. Good.
Sample2: 5 a 1 b 2 c 2 d 4 e 3 5 b a a c c d e b c b
Map accordingly. Graph: all connected, size=5 min=1 => total=5. Good.
Thus answer.
But the problem statement in the sample input 2 shows "Five" maybe a typo. We'll ignore.
Now, for completeness, what about if M > 0 but there are isolated nodes? Those are components of size1.
Thus answer.
Now, I'll produce final solution.
But also think about the possibility of directed magic? The problem says: "The i-th magic can be changed to the material t_i by applying it to the material s_i, and conversely to s_i by applying it to the material t_i." So it's undirected/bidirectional. So graph is undirected.
Now, all good.
Now, final answer.
We need to output integer.
Thus solved.
I'll write the solution in Python 3.
Potential optimization: Could also use union-find (DSU) to find components and then aggregate by root: For each node, union(s_i, t_i). Then for each node, find root, accumulate component size and min price. That would be even simpler and O(N α(N) + M α(N)). But DFS is fine.
I'll use DSU for simplicity and to avoid recursion/stack. But both okay.
Given N=5000, M=1000, either is fine.
I'll implement DSU:
parent = list(range(N)) rank or size optional.
Define find(x): if parent[x]!=x: parent[x]=find(parent[x]); return parent[x]. Union(u,v): ru=find(u); rv=find(v); if ru!=rv: parent[rv]=ru (or union by rank).
After processing edges, create a dictionary mapping root to (size, min_price). Initialize: for i in range(N): root = find(i); then update size[root] += 1; min_price[root] = min(min_price[root], price[i]).
Then total = sum(size[root] * min_price[root] for root in dict). That works.
Since names mapping needed only for edges, we can map names to indices.
I'll code with DSU.
Edge Cases: If M=0, each node is its own root, then each component size=1, min=price, sum = sum(prices. Works.
So solution with DSU:
- Read N.
- For i in range(N): read name, price; store in list prices[i]; also store name_to_idx[name]=i.
- Read M.
- Initialize DSU parent = list(range(N)).
- For each magic: read s, t; u = name_to_idx[s]; v = name_to_idx[t]; union(u, v).
- After unions, create dict comp = {} mapping root -> [size, min_price].
- For i in range(N): r = find(i); if r not in comp: comp[r]=[0, large]; then comp[r][0] += 1; comp[r][1] = min(comp[r][1], prices[i]).
- total = sum(size * min_price for size, min_price in comp.values())
- print(total)
Complexities: O(N + M α(N)) fine.
Now ensure find uses path compression.
I'll implement union by size/rank to make it efficient but not necessary.
Now code.
Testing on sample.
Now I'll produce final answer.
But I recall sometimes problem might have trick: The magic can be used on a single material repeatedly, but maybe you could also use a material to produce multiple materials by some kind of splitting? Not mentioned. So no.
Thus final.
Now I'll produce the final answer with explanation. ```python
import sys
def main(): data = sys.stdin.read().strip().splitlines() if not data: return it = iter(data)
N = int(next(it).strip()) prices = [0] * N name_to_idx = {} for i in range(N): parts = next(it).split() name = parts[0] price = int(parts[1]) prices[i] = price name_to_idx[name] = i M = int(next(it).strip()) # ---------- DSU ---------- parent = list(range(N)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x def union(a, b): ra = find(a) rb = find(b) if ra != rb: parent[rb] = ra # simple union, size/rank not needed for N=5000 # read edges and unite for _ in range(M): s, t = next(it).split() u = name_to_idx[s] v = name_to_idx[t] union(u, v) # aggregate per component comp_info = {} # root -> [size, min_price] for i in range(N): r = find(i) if r not in comp_info: comp_info[r] = [0, 10**9] # price <= 1000, so big sentinel ok comp_info[r][0] += 1 comp_info[r][1] = min(comp_info[r][1], prices[i]) total = 0 for size, minp in comp_info.values(): total += size * minp print(total)if name == "main": main()