Description

Submission

class Solution {
    typedef pair<int, int> PII;
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> ptrs(primes.size(), 0);

        priority_queue<PII, vector<PII>, greater<>> pq;
        vector<int> arr;
        arr.push_back(1);

        for(int i = 0; i < primes.size(); ++i) {
            pq.emplace(arr[ptrs[i]] * primes[i], i);
        }

        for(int i = 0; i < n - 1; ++i) {
            auto val = pq.top().first;
            arr.push_back(val);
            
            while(val == pq.top().first) {
                auto [cur, idx] = pq.top();
                pq.pop();
                ++ptrs[idx];
                pq.emplace(arr[ptrs[idx]] * primes[idx], idx);
            }
        }

        return arr.back();
    }
};

// the next number: min(arr[ptrs[i]] * primes[i], ...., )