Problem statement

https://binarysearch.com/problems/Low-Score/

Solution 1

First idea is to use dp with states (node, steps), where node is current node we reached and steps is number of steps we made.

Complexity

It is O(n * E). Unfortunatelly it will give TLE, because we have a lot of jumps in our cache.

Code 1


class Solution:
    def solve(self, edges):
        G, INF = defaultdict(list), 200000000
        n = max(max(i for i, _, _ in edges), max(j for _, j, _ in edges)) + 1
        for u, v, w in edges:
            if u != v: G[v] += [(u, w)]
            if u != v: G[u] += [(v, w)]

        @lru_cache(None)
        def dp(node, steps):
            if steps == 0: return INF * (node != 0)
            
            ans = INF
            for ch, w in G[node]:
                q = dp(ch, steps - 1)
                if q == INF or steps == 1:
                    prev = q
                else:
                    prev = q//(steps - 1)
                ans = min(ans, max(w, prev)*steps)

            return ans

        return min([dp(n-1, i) for i in range(1, n)])

Code 2

Even after making it tabular it is still gives TLE.

class Solution:
    def solve(self, edges):
        G, INF = [], 200000000
        n = max(max(i for i, _, _ in edges), max(j for _, j, _ in edges)) + 1
        for u, v, w in edges:
            if u != v: 
                G += [(u, v, w)]
                G += [(v, u, w)]

        dp = [[INF]*n for _ in range(n)]
        dp[0][0] = 0

        for steps in range(1, n):
            for u, v, w in G:
                q = dp[steps-1][v]
                prev = q if (q == INF or steps == 1) else q//(steps - 1)
                dp[steps][u] = min(dp[steps][u], max(w, prev)*steps)

        return min(dp[x][-1] for x in range(n))

Solution 2

Alternative solution is to use a lot of bfs: add edge by edge, sorted by weight and check the shortest path.

Complexity

It is still O(n*E), but now it works much faster.

Code

class Solution:
    def solve(self, edges):
        edges.sort(key=lambda e: e[2])
        n = max(max(i for i, _, _ in edges), max(j for _, j, _ in edges)) + 1
        
        G = defaultdict(dict)
        ans = INF = 200000000
        
        def bfs():
            queue, dist = [0], {0: 0}
            for node in queue:
                if node == n - 1:
                    return dist[node] # dist for last node
                for nei in G[node]:
                    if nei not in dist:
                        dist[nei] = dist[node] + 1
                        queue.append(nei)
            return INF
        
        for u, v, w in edges: 
            G[u][v] = G[v][u] = w
            ans = min(ans, bfs() * w)
           
        return ans if ans < INF else -1