Timeline (USACO Gold 2020 February)

这个题比较简单，比较容易想到用图来表示关系，“记忆”三元组 $(a,b,x)$ 就是图上从 $a$ 到 $b$ 的一条长度为 $x$ 的边。然后挤奶事件之间的依赖关系就组成了一个DAG，可以进行topological sort。

完成拓扑排序后，就可以依次计算每个点的的最早时间：等于自己的最早时间，以及“前辈最早时间 + 入度边长”之间在的最大值。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, m, C;
vector<pair<int,int>> adj[100005], back[100005];      // node, delay 
int in_degree[100005];
int dp[100005];     // i no earlier than dp[i]
 
int main() {
    scanf("%d %d %d", &n, &m, &C);
    for (int i = 1; i <= n; i++)
        scanf("%d", &dp[i]);
    for (int i = 0; i < C; i++) {
        int u,v,t;
        scanf("%d %d %d", &u, &v, &t);
        adj[u].push_back({v, t});
        back[v].push_back({u, t});
        in_degree[v]++;
    }
 
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (in_degree[i] == 0) q.push(i);
    
    while (!q.empty()) {    // scan nodes in topological order
        int x = q.front();
        q.pop();
        for (auto e: adj[x]) {
            int y = e.first;
            if ((--in_degree[y]) == 0)
                q.push(y);
        }
        for (auto e: back[x]) { // find earliest time
            int y = e.first, t = e.second;
            dp[x] = max(dp[x], dp[y] + t);
        }
    }
    for (int i = 1; i <= n; i++)
        printf("%d\n", dp[i]);
 
    return 0;
}