Editorial for Nuclear Waste

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

Solve the problem in three Bellman-Ford-style passes.

Pass 1. Compute how far each location is from the nearest nuclear waste site. Treat the given directed edges as undirected and run multi-source Bellman-Ford from every waste location. Call this value $waste[v]$ ~waste[v]~.

Pass 2. The safety of a route is the minimum $waste[v]$ ~waste[v]~ over vertices $v$ ~v~ on the route. Maximize safety from $1$ ~1~ to $n$ ~n~ with another Bellman-Ford: the state at each node is the best bottleneck so far, and relaxing $a \to b$ ~a \to b~ yields $\min(safety[a], waste[b])$ ~\min(safety[a], waste[b])~.

Pass 3. Among routes that achieve that maximum safety $S$ ~S~, maximize total food. Restrict to nodes with $waste[v] \ge S$ ~waste[v] \ge S~ (any visit below $S$ ~S~ would drop safety). Run Bellman-Ford maximizing food on that subgraph.

After $n - 1$ ~n - 1~ food relaxations, the value at node $n$ ~n~ is optimal among simple routes. Then run $n$ ~n~ further relaxations and check whether the food at $n$ ~n~ alone increases. The first of those $n$ ~n~ iterations updates nodes on a positive-food cycle (if any); up to $n - 1$ ~n - 1~ more may be needed for that improvement to reach $n$ ~n~. If $n$ ~n~'s food changes, output -1.

With $n \le 200$ ~n \le 200~ and $m \le 500$ ~m \le 500~, the time complexity $O(nm)$ ~O(nm)~ is acceptable.

Solution (Python)

import sys

INF = 10**30
NEG_INF = -INF


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, m, w_count = data[0], data[1], data[2]
    wastes = [x - 1 for x in data[3 : 3 + w_count]]
    idx = 3 + w_count

    edges: list[tuple[int, int, int, int]] = []
    rev_edges: list[tuple[int, int, int]] = []
    for _ in range(m):
        fro = data[idx] - 1
        to = data[idx + 1] - 1
        weight = data[idx + 2]
        food = data[idx + 3]
        idx += 4
        edges.append((fro, to, weight, food))
        rev_edges.append((to, fro, weight))

    # Pass 1: undirected distance from the nearest waste site.
    waste_dist = [INF] * n
    for site in wastes:
        waste_dist[site] = 0

    for _ in range(n - 1):
        updated = False
        for fro, to, weight, _ in edges:
            if waste_dist[fro] == INF:
                continue
            cand = waste_dist[fro] + weight
            if cand < waste_dist[to]:
                waste_dist[to] = cand
                updated = True
        for fro, to, weight in rev_edges:
            if waste_dist[fro] == INF:
                continue
            cand = waste_dist[fro] + weight
            if cand < waste_dist[to]:
                waste_dist[to] = cand
                updated = True
        if not updated:
            break

    # Pass 2: maximum path safety (bottleneck) from 1 to n.
    safety = [NEG_INF] * n
    safety[0] = waste_dist[0]

    for _ in range(n - 1):
        updated = False
        for fro, to, _, _ in edges:
            if safety[fro] == NEG_INF:
                continue
            cand = min(safety[fro], waste_dist[to])
            if cand > safety[to]:
                safety[to] = cand
                updated = True
        if not updated:
            break

    target_safety = safety[n - 1]

    # Pass 3: maximum food among routes that keep safety == target_safety.
    # Only visit nodes whose waste distance is at least target_safety.
    food = [NEG_INF] * n
    if waste_dist[0] >= target_safety:
        food[0] = 0

    for _ in range(n - 1):
        updated = False
        for fro, to, _, edge_food in edges:
            if food[fro] == NEG_INF or waste_dist[to] < target_safety:
                continue
            cand = food[fro] + edge_food
            if cand > food[to]:
                food[to] = cand
                updated = True
        if not updated:
            break

    finite_food = food[n - 1]

    # One more full n iterations: a positive-food cycle updates on the first of
    # these, and up to n-1 further iterations may be needed for that improvement
    # to reach node n.
    for _ in range(n):
        for fro, to, _, edge_food in edges:
            if food[fro] == NEG_INF or waste_dist[to] < target_safety:
                continue
            cand = food[fro] + edge_food
            if cand > food[to]:
                food[to] = cand

    ans_food = food[n - 1]
    if ans_food != finite_food:
        ans_food = -1
    print(target_safety, ans_food)


if __name__ == "__main__":
    main()

Comments

There are no comments at the moment.