Editorial for Charged Courier

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Use dynamic programming over the amount of battery already spent.

Let $dp[x][v]$ ~dp[x][v]~ be the maximum reward possible after reaching city $v$ ~v~ having spent exactly $x$ ~x~ battery units. Initially, $dp[0][1] = 0$ ~dp[0][1] = 0~ and all other states are unreachable.

Process battery amounts from $0$ ~0~ to $B$ ~B~. From each reachable state $dp[x][u]$ ~dp[x][u]~, try every road $u \to v$ ~u \to v~ with reward $r$ ~r~ and cost $c$ ~c~. If $x + c \le B$ ~x + c \le B~, update:

$dp[x + c][v] = \max(dp[x + c][v], dp[x][u] + r)$

This works even when the graph has directed cycles, because every road has positive battery cost. Every transition strictly increases the spent battery, so states only move forward in the DP order.

The answer is the maximum value of $dp[x][N]$ ~dp[x][N]~ over all $0 \le x \le B$ ~0 \le x \le B~. If no such state is reachable, output -1.

The time complexity is $O(B(N + M))$ ~O(B(N + M))~.

Solution (Python)

import sys


def main() -> None:
    input = sys.stdin.readline
    n, m, b = map(int, input().split())

    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v, reward, cost = map(int, input().split())
        if cost <= b:
            graph[u].append((v, reward, cost))

    neg = -10**30
    dp = [[neg] * (n + 1) for _ in range(b + 1)]
    dp[0][1] = 0

    for spent in range(b + 1):
        row = dp[spent]
        for city in range(1, n + 1):
            cur = row[city]
            if cur == neg:
                continue
            for nxt, reward, cost in graph[city]:
                new_spent = spent + cost
                if new_spent <= b:
                    val = cur + reward
                    if val > dp[new_spent][nxt]:
                        dp[new_spent][nxt] = val

    ans = max(dp[spent][n] for spent in range(b + 1))
    print(ans if ans != neg else -1)


if __name__ == "__main__":
    main()

Comments

There are no comments at the moment.