Python 3: FT 94%: Modified Dijkstra, Hard to Solve, but Surprisingly Straightforward To Code Up
Intuition\n\nThe tough part of this problem IMO is convincing yourself that whatever algorithm you come up with won\'t give you TLE.\n\nA big part of that is to
# Intuition\n\nThe tough part of this problem IMO is convincing yourself that whatever algorithm you come up with won\'t give you TLE.\n\nA big part of that is to notice that\n* the minimum `time` between any two edges is `10` or more\n* and the `maxTime` is at most 100\n* therefore each path can have at most 11 nodes in it, 9 other than 0\n\nAlso notice that there are at most four edges.\n\nSo a worst-case-ish scenario is where `0` is connected to four other nodes that are cheap, and those four are connected each to three more, and so on.\n\nThe total paths would be `4 ** 10` because there are 10 choices, or about 1e6 paths. That\'s on the cusp of TLE but slightly below.\n\nThen don\'t forget that\n* 4 choices per path is the absolute worst case, most of the time we\'ll have many fewer\n* the fact we must start and end at 0 means that only four nodes connect to zero, and the penultimate node in the loop back to zero must also be one of these nodes, which limits the number of paths we\'ll explore\n* and also we can recognize that **if we have several ways to visit nodes `{n1, n2, ..., nk}` ending with a certain node `n_i`, only the shortest one will give the best answer in general**\n* therefore to have `1e6` unique paths we\'d need a lot more than "just" 1e3 nodes\n\nAll of these will conspire to reduce the number of paths we explore.\n\n# Modified Dijkstra\n\nThe key insight is the bolded statement above:\n* suppose we have some set `vis` of visited nodes for some path\n* and that path ends at `u`\n* then we only want to explore more nodes from the *shortest* path for `(vis, u)`\n\nTherefore we want to pop `(vis, u)` combinations in order by total time taken. That way we only explore (or "relax" in graph terminology) from each set of nodes and origin once, with the minimum time.\n\n**This is what Dijkstra\'s algorithm does.** It pops paths in order by min cost (time in this case), and we only relax from the minimum time for each state.\n\n# Approach\n\nFor Dijkstra we need to\n* record the minimum time for each `(vis, u)` combination\n  * one option is to use a bit set for `vis` and an int for `u`, but there are 1000 nodes so the bit set would have `O(n)` memory. Yikes.\n  * another option is to **use a `frozenset` of the visited nodes** so that we get `O(1)` memory used to mark each node, `O(1)` lookup, and still be able to hash it\n  * note that `set` is NOT hashable since it\'s mutable. `frozenset`s are immutable and thus hashable; this is the main reason they exist in Python\n* also have a heap of `(totalTime, currentNode, visitedNodes)`\n  * this is a mean heap by `totalTime` ascending\n\nWhat I implement in the code is the "poor man\'s Python version" of Dijkstra.\n* we use a heap as a priority queue\n* priority queues don\'t support decreasing the key of an arbitrary element, so we don\'t. If we find a new best time for `(vis, u)` we just push the new `(newBestTime, vis, u)` to the heap.\n* therefore we have a quick "if this isn\'t the best time, then this element is stale and was superceded by a better time, so skip this element" check\n\nThe consequence is `O(E)` memory use instead of `O(V)`.\n\nIf you want `O(V)` you MUST use a "priority queue" that supports updating the priority of elements. Common options include\n* a custom data structure where you can reduce the key, such as a custom heap implementation where you record the current index in the heap of each element. That way you can change the priority, then repair the heap starting at that element\'s current location\n* a combination of a tree set and a hash set\n  * if you find a new state `(vis, u)` and the new time is lower, then\n  * remove `(time, vis, u)` from the tree set to remove the old entry\n  * add `(time, vis, u)` to the tree set\n  * and now you can have just one entry in the tree set for each `(vis, u)` AND do updates and pop the min element in `log(entries)` time\n\n# Complexity\n\n- Time complexity: roughly `O(4**(maxTime/time) * maxTime/time * log(4**(maxTime/time)) * maxTime/time)` in the absolute worst case where we have a ton of nodes, they all have four edges, and all edges have the same value of time. Anything else (e.g. some edges having large `time` values) will reduce the complexity.\n  - we can travel over `maxTime/time` edges so that\'s the max number of nodes in the path plus one\n  - for each node in the path there are at most 4 destination nodes to choose from\n  - the heap we have will have roughly `4**(maxTime/time) * maxTime/time` entries in it. The first part is the number of paths, and the second part is because we include the time of each endpoint as well; if it\'s a ring of `k` nodes that takes `totalTime` to visit then we\'ll have `(vis, u)` with the same `totalTime` for all `k` nodes in the ring\n\n- Space complexity: same as time? idk the complexity analysis for this is hard\n\n# Code\n```python3 []\nclass Solution:\n    def maximalPathQuality(self, values: List[int], edges: List[List[int]], T: int) -> int:\n        # undir graph nodes 0..n-1\n        # edges are [u, v, time]..\n        #    takes time to go between u and v\n        \n        N = len(values)\n\n        # valid path takes up to maxTime seconds\n        # quality of path is the sum of values of unique nodes on the path\n\n        # return max quality of any path\n\n        # 1000 nodes, at most 2000 edges\n\n        # at most 4 edges of any node\n\n        #### what about all paths of length 0? just nodes\n        #   all paths of length 1: a node and another node\n\n        # all paths of length L:\n        #      if I have paths of length L1 ending at u\n        #      and paths of length L2 ending at v\n        #      and u--v has dist L3\n        #      then that contributes to L=L1+L2+L3\n\n        # but all paths is a huge number of paths\n        # and all pairwise interactions might matter\n\n        #################\n\n        # time, maxTime in 10..100 so we can visit at most 11 total nodes\n        #\n        # so the Dijkstra or SPFA-like algo should work well here\n\n        adj = [[] for _ in range(N)]\n\n        for u, v, t in edges:\n            if t > T: continue\n            adj[u].append((v, t))\n            adj[v].append((u, t))\n\n        # points only depend on unique nodes\n        #    > so we only care about uniques, duh\n        #    > and the time required\n        #    > connectivity is about where we are currently b/c path must be connected\n\n        min_time = {(frozenset([0]), 0): 0} # visited, currNode\n        \n        pq = [(0, 0, frozenset([0]))] # time, currNode, visited\n        while pq:\n            time, u, visited = heappop(pq)\n\n            if min_time[(visited, u)] > time: continue # stale entry\n\n            for v, t in adj[u]:\n                vis_v = visited | {v}\n                t_v = time + t\n\n                if t_v > T or t_v >= min_time.get((vis_v, v), math.inf): continue\n\n                min_time[(vis_v, v)] = t_v\n                heappush(pq, (t_v, v, vis_v))\n\n        return max(sum(values[v] for v in visited) for visited, v in min_time if v == 0)\n```
['Python3']