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

First compute how far each location is from the nearest nuclear waste site. Treat the given directed edges as undirected for this step and run Bellman-Ford (or any multi-source shortest-path algorithm) from every waste location. Call this value $waste[v]$ ~waste[v]~.

The safety of a route is the minimum $waste[v]$ ~waste[v]~ over vertices $v$ ~v~ on the route. Maximize safety; among routes with the same safety, maximize total food.

Run another Bellman-Ford-style relaxation on the directed graph, where the state at each node is the lexicographic pair $(safety, food)$ ~(safety, food)~. Relaxing edge $a \to b$ ~a \to b~ with food $d$ ~d~ produces the candidate pair with safety $\min(safety[a], waste[b])$ ~\min(safety[a], waste[b])~ and food $food[a] + d$ ~food[a] + d~. Keep the better pair at each node.

After $n - 1$ ~n - 1~ relaxations, the food value at node $n$ ~n~ is finite if no improving cycle remains. Running $n - 1$ ~n - 1~ further relaxations and checking whether the food at $n$ ~n~ increases detects a positive-food cycle that preserves the optimal safety; in that case output -1 for food.

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 better(a: tuple[int, int], b: tuple[int, int]) -> bool:
    if a[0] != b[0]:
        return a[0] > b[0]
    return a[1] > b[1]


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))

    # Undirected distances 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

    # Maximize (path safety, food), where safety is the minimum waste_dist on the path.
    best = [(NEG_INF, NEG_INF) for _ in range(n)]
    best[0] = (waste_dist[0], 0)

    for _ in range(n - 1):
        updated = False
        for fro, to, weight, food in edges:
            if best[fro][0] == NEG_INF:
                continue
            cand = (min(waste_dist[to], best[fro][0]), best[fro][1] + food)
            if better(cand, best[to]):
                best[to] = cand
                updated = True
        if not updated:
            break

    finite_food = best[n - 1][1]

    for _ in range(n - 1):
        updated = False
        for fro, to, weight, food in edges:
            if best[fro][0] == NEG_INF:
                continue
            cand = (min(waste_dist[to], best[fro][0]), best[fro][1] + food)
            if better(cand, best[to]):
                best[to] = cand
                updated = True
        if not updated:
            break

    safety, food = best[n - 1]
    if food != finite_food:
        food = -1
    print(safety, food)


if __name__ == "__main__":
    main()

Comments

There are no comments at the moment.