C++ O(n*2k), O(n*k), O(n*k*logk) solutions
Time: O(n2k), 36ms.\n\nclass Solution {\npublic:\n    int nthSuperUglyNumber(int n, vector<int>& primes) {\n        vector<int>dp(n);\n        dp[0] = 1;\n     
**Time:** O(n*2k), 36ms.\n```\nclass Solution {\npublic:\n    int nthSuperUglyNumber(int n, vector<int>& primes) {\n        vector<int>dp(n);\n        dp[0] = 1;\n        vector<int>p(primes.size());\n        for(int i = 1; i < n; i++){\n            dp[i] = INT_MAX;\n            for(int j = 0; j < p.size(); j++) dp[i] = min(dp[i], dp[p[j]] * primes[j]);\n            for(int j = 0; j < p.size(); j++) if(dp[p[j]] * primes[j] == dp[i]) p[j]++;\n        }\n        return dp[n - 1];\n    }\n};\n```\n***\nImprove from 2 inner loops to one loop, idea from this [post](https://discuss.leetcode.com/topic/34841/java-three-methods-23ms-36-ms-58ms-with-heap-performance-explained).\n**Time:** O(nk), 23ms, beats 97.16%\n```\nclass Solution {\npublic:\n    int nthSuperUglyNumber(int n, vector<int>& primes) {\n        vector<int>dp(n);\n        vector<int>p(primes.size());\n        vector<int>val(primes.size());\n        int next = 1;\n        for(int i = 0; i < n; i++){\n            dp[i] = next;\n            next = INT_MAX;\n            for(int j = 0; j < val.size(); j++){\n                if(dp[i] >= val[j]) val[j] = dp[p[j]++] * primes[j];\n                next = min(next, val[j]);\n            }\n        }\n        return dp[n - 1];\n    }\n};\n```\n***\nAlso, I wrote the last `heap` C++ version from the same post, but I think its time complexity is in worst case O(nklogk) rather than O(nlogk), which is actually slower than above solution.\n**Time:** O(nklogk), 65ms. \n```\nstruct triple{\n    int val;\n    int prime;\n    int p;\n    triple(int x, int y, int z):val(x), prime(y), p(z){};\n};\n\nclass Solution {\npublic:\n    int nthSuperUglyNumber(int n, vector<int>& primes) {\n        vector<int>dp(n);\n        dp[0] = 1;\n        auto cmp = [](triple* t1, triple* t2){ return t1->val > t2->val; };\n        priority_queue<triple*, vector<triple*>, decltype(cmp)>pq(cmp);\n        for(int i = 0; i < primes.size(); i++) pq.push(new triple(primes[i], primes[i], 1));\n        for(int i = 1; i < n; i++){\n            dp[i] = pq.top()->val;\n            while(pq.top()->val == dp[i]){\n                triple* t = pq.top();\n                pq.pop();\n                pq.push(new triple(t->prime * dp[t->p], t->prime, t->p + 1));\n            }\n        }\n        return dp[n - 1];\n    }\n};\n```
['C++']