Overview

This problem requires finding the cheapest store for each product’s category, determining whether all products can be purchased, and if possible, computing the minimum total cost.

Analysis

The key observations are as follows: - For products of the same category, it is optimal to purchase them at the lowest price among all stores that handle that category - If there exists even one product whose category is not handled by any store, it is impossible to purchase all products - As a naive approach, searching through all stores for each product to find the lowest price results in a time complexity of \(O(N \times M)\), which under the constraints (\(N, M \leq 2 \times 10^5\)) would require up to \(4 \times 10^{10}\) operations, making it impossible to meet the time limit

Algorithm

1. Preprocessing: Scan all store information and record the cheapest price for each category in a dictionary
2. Check: Verify whether each product category in the shopping list exists in the dictionary. If even one category does not exist, output -1
3. Calculation: If all categories exist, compute the total cost by summing up the cheapest price for each product

Complexity

• Time complexity: \(O(N + M)\)
  • Processing store information takes \(O(M)\)
  • Processing the product list takes \(O(N)\)
• Space complexity: \(O(K)\) (where \(K\) is the number of distinct categories)
  • Size of the dictionary recording the cheapest prices

Implementation Notes

• By using defaultdict to initialize access to non-existent keys with float('inf'), existence checks become straightforward later

• When parsing input data, index management must be handled precisely

• When processing store information, the minimum price is updated each time the same category appears

• Early return: As soon as an impossible category is found, immediately output -1 and terminate processing

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        print(-1)
        return
        
    n = int(data[0])
    m = int(data[1])
    T = list(map(int, data[2:2+n]))
    shops = []
    index = 2 + n
    for i in range(m):
        s = int(data[index])
        c = int(data[index+1])
        index += 2
        shops.append((s, c))
        
    from collections import defaultdict
    category_min_price = defaultdict(lambda: float('inf'))
    
    for s, c in shops:
        if c < category_min_price[s]:
            category_min_price[s] = c
            
    total = 0
    for t in T:
        if t not in category_min_price:
            print(-1)
            return
        total += category_min_price[t]
        
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.