[C++] TSP - Hamiltonian Path (Not tour) - Simple code
\n#define INF 0x3f3f3f3f\n\nclass Solution {\n    int VISITED_ALL, n;\n    vector < vector < int > > dist, path, dp;\npublic:\n    int calcDist(string a, string
```\n#define INF 0x3f3f3f3f\n\nclass Solution {\n    int VISITED_ALL, n;\n    vector < vector < int > > dist, path, dp;\npublic:\n    int calcDist(string a, string b){\n        for(int i = 0; i < a.length(); i++)\n            if(b.rfind(a.substr(i), 0) == 0)\n                return b.length() - (a.length() - i);\n        return b.length();\n    }\n    \n    int tsp(int mask, int pos){\n        if(mask == VISITED_ALL)\n            return 0;\n        if(dp[mask][pos] != -1)\n            return dp[mask][pos];\n        \n        int ans = INF, best;\n        \n        for(int city = 0; city < n; city++){\n            if((mask & (1 << city)) == 0){\n                int result = dist[pos][city] + tsp(mask | (1 << city), city);\n                if(result < ans){\n                    ans = result;\n                    best = city;\n                }\n            }\n        }\n        path[mask][pos] = best;\n        return dp[mask][pos] = ans;\n    }\n    \n    string constructPath(vector < string > &A, int k){\n        int curr = k;\n        string result = A[k];\n        int mask = (1 << k);\n        int parent = path[mask][k];\n        while(parent != -1){\n            result += A[parent].substr(A[parent].length() - dist[curr][parent]);\n            mask |= (1 << parent);\n            curr = parent;\n            parent = path[mask][parent];\n        }\n        return result;\n    }\n    \n    string shortestSuperstring(vector<string>& A) {\n        n = A.size();\n        VISITED_ALL = (1 << n) - 1;\n        \n        dist.assign(n, vector < int > (n, 0));\n        \n        for(int i = 0; i < n; i++)\n            for(int j = 0; j < n; j++)\n                dist[i][j] = calcDist(A[i], A[j]);\n        \n        int ansLen = INF;\n        string ans;\n        \n        // for different starting nodes\n        for(int k = 0; k < n; k++){\n            path.assign((1 << n), vector < int > (n, -1));\n            dp.assign((1 << n), vector < int > (n, -1));\n\n            tsp((1 << k), k);\n            \n            string result = constructPath(A, k);\n            // cout << result << endl;\n            if(result.length() < ansLen){\n                ans = result;\n                ansLen = result.length();\n            }\n        }\n        return ans;\n    }\n};\n```
['Dynamic Programming', 'C', 'Bitmask', 'C++']