Timeline

February 2020, Gold - Problem 1: timeline

Algorithm

We can model the problem as a directed acyclic graph (DAG). We start by adding n vertices (one for each milking session), then add a vertex k with edges going to each session i with length S_i. Then, for each memory triple (a,b,x), we draw an edge from vertex a to vertex b with length x. The answer for session i is the length of the longest path from k to i.

To find the length of the longest path, we first use topological sort to order the vertices in a way that each edge points to a vertex later in the array. We then process each vertex a in our topologically sorted array. Initialize an array res, to store the current longest path for each session. For each neighbor b of a, we set its currently longest path to max(res[b], res[a]+x) where x is the length of the edge (a,b). After we process all the vertices, res will contain the earliest date for each milking session.

Python

def setio(name):
    # Overwrites input/print functions to file io
    global input, print
    f = open(f"{name}.in","r")
    o = open(f"{name}.out","w")
    input = f.readline
    print = o.write

def intline():
    # Get one-line list of space separated ints
    return list(map(int, input().split()))

# Get Input
setio("timeline")
n, m, c = intline()
res = [0]+intline() # S_i; edges are 1-indexed so we pad a 0

adj = [[] for _ in range(n+1)]
indegree = [0] * (n+1)

for _ in range(c):
    # (a, b, x)
    s = intline()
    adj[s[0]].append([s[1], s[2]])
    indegree[s[1]] += 1

# Kahn's algorithm (Topological Sort)
topsorted = []
queue = []
for i in range(1, n+1):
    if indegree[i] == 0:
        queue.append(i)
while queue:
    a = queue.pop()
    topsorted.append(a)
    for edge in adj[a]:
        b, x = edge
        indegree[b] -= 1 # Remove edge from graph
        # If b has no incoming edges, then add to queue
        if indegree[b] == 0:
            queue.append(b)

# Solve
for a in topsorted:
    for edge in adj[a]:
        b, x = edge
        # If a longer path is found, update res
        res[b] = max(res[b], res[a]+x)

print("\n".join(map(str,res[1:]))+"\n")