s4553711
5/21/2017 - 2:29 PM

313.cpp

struct Node {
	int val,index,prime;
	Node(int index,int val,int prime):index(index),val(val),prime(prime){}
	bool operator < (const Node &b)const {
		return val > b.val;
	}
};

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> result(n, 0);
        result[0] = 1;
        priority_queue<Node> q;
        for(int j = 0; j < primes.size(); j++) {
            q.push(Node(0, primes[j], primes[j]));
        }
        for(int i = 1; i < n; i++) {
            Node cur = q.top();
            result[i] = cur.val;
            do {
                cur = q.top(); q.pop();
                cur.val = cur.prime * result[++cur.index];
                q.push(cur);
                
            } while(!q.empty() && q.top().val == result[i]);
        }
        return result[n-1];
    }
};