Shortest Path Problem (Directed acyclic graph with nonnegative weights)
Treat (last word, used words bitmask) as a node, then\n\nd((i, mska), (j, mskb)) = len(j) - overlap(i,j) if (mska | (1<<j) == mskb) and (mska & (1<<j) == 0) and
Treat (last word, used words bitmask) as a node, then\n```\nd((i, mska), (j, mskb)) = len(j) - overlap(i,j) if (mska | (1<<j) == mskb) and (mska & (1<<j) == 0) and (mska & (1<<i) != 0)\n                          else  INF\n```\nAnd add 2 extra nodes S and T:\n```\nd(S, (i, 1<<i)) = len(i)\nd((i, ALL_NODES), T) = 0\n(0 <= i < N)\n```\nThen our job is finding the shortest path from S to T.\n\nThis reminded me Dijkstra\'s Algorithm:\n```python\nfrom heapq import heappush, heappop, heapify\n\nclass Solution:\n    def shortestSuperstring(self, A):\n        """\n        :type A: List[str]\n        :rtype: str\n        """\n        N = len(A)\n        add = [[0]*N for _ in range(N)]\n        \n        def calc_add(a, b):\n            for i in range(min(len(a), len(b)), 0, -1):\n                if a[-i:] == b[0:i]:\n                    return len(b) - i\n            return len(b)\n        \n        for i in range(N):\n            for j in range(N):\n                if i != j:\n                    add[i][j] = calc_add(A[i], A[j])\n        \n        all_nodes = (1 << N) - 1\n        v = [[False] * (1 << N) for _ in range(N)]\n        hq = [[len(A[i]), i, 1 << i, A[i]] for i in range(N)]\n        heapify(hq)\n        while hq:\n            l, i, msk, s = heappop(hq)\n            if msk == all_nodes: return s\n            if v[i][msk]: continue\n            v[i][msk] = True\n            for j in range(N):\n                if i == j or (1 << j) & msk: continue\n                nmsk = msk | (1 << j)\n                if v[j][nmsk]: continue\n                heappush(hq, [l+add[i][j], j, nmsk, s + A[j][-add[i][j]:]])\n        return -1\n```\nTime complexity for Dijkstra\'s Algorithm(with binary heap) is O((E+V)logV), here V = N * 2^N and E \u2252 N^2 * 2^N\nSo time complexity of this approach is O(N^3 * 2^N * log N).\nI got TLE during the contest with python but got AC with C++.\n\nIn fact, since this graph is acyclic, we can solve it in O(E+V) time with topological sorting (actually it is dp). \nSee https://en.wikipedia.org/wiki/Shortest_path_problem#Directed_acyclic_graphs\nand https://en.wikipedia.org/wiki/Topological_sorting#Application_to_shortest_path_finding\n\nHere\'s the code and its time complexity is O(N^2 * 2^N):\n```python\nclass Solution:\n    def shortestSuperstring(self, A):\n        """\n        :type A: List[str]\n        :rtype: str\n        """\n        N = len(A)\n        add = [[0]*N for _ in range(N)]\n        \n        def calc_add(a, b):\n            for i in range(min(len(a), len(b)), 0, -1):\n                if a[-i:] == b[0:i]:\n                    return len(b) - i\n            return len(b)\n        \n        for i in range(N):\n            for j in range(N):\n                if i != j:\n                    add[i][j] = calc_add(A[i], A[j])\n        \n        all_nodes = (1 << N) - 1\n        INF = float(\'inf\')\n        dp = [[(INF, \'\')] * N for i in range(1 << N)]\n        for i in range(N):\n            dp[1<<i][i] = len(A[i]), A[i]\n        \n        for msk in range(1<<N):\n            for i in range(N):\n                if not msk & (1 << i): continue\n                for j in range(N):\n                    if msk & (1 << j): continue\n                    nmsk = msk | (1 << j)\n                    if dp[nmsk][j][0] >= dp[msk][i][0] + add[i][j]:\n                        dp[nmsk][j] = dp[msk][i][0] + add[i][j], dp[msk][i][1] + A[j][-add[i][j]:]\n        return min(dp[all_nodes])[1]\n```
[]