题解

翻译：

思路：

我们可以用 拓扑排序$(TopoSort)$ 配合 动态规划$(Dynamic\,\,Programming)$ 来解决这道题。可以把三元组 $(a,b,x)$ 抽象成图中结点 $a$ 到结点 $b$ 的一条有向边，边权为 $x$。

先将输入数据存正向图以及它的反向图，并记录正向图中结点的入度，接着根据正向图进行拓扑排序，然后利用拓扑排序序列进行动态规划更新当前结点的答案。因为我们要求最早日期，所以可以用贪心思想，直接和每个 $x$ 进行比较，这样能够得到最早日期。

---

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pir pair<int,int>
#define x first
#define y second
#define pb push_back
#define ins insert
#define endl '\n'
const int N=1e5+10;
int n,m,c,u,v,w,s[N],dp[N],in[N];
vector<pir>hparg[N];
vector<int>toposort,graph[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>c;
    for(int i=1;i<=n;i++)cin>>s[i];
    while(c--){
        cin>>u>>v>>w;
        graph[u].pb(v); //存正向图，只需要存编号
        hparg[v].pb({u,w}); //存反向图
        in[v]++; //入度
    }
    //拓扑排序
    queue<int>q; //不需要用priority_queue获得最小字典序列
    for(int i=1;i<=n;i++)if(!in[i])q.push(i);
    while(q.size()){
        int u=q.front();
        q.pop();
        toposort.pb(u);
        for(auto v:graph[u]){
            if(--in[v])continue;
            q.push(v);
        }
    }
    //根据反向图推出答案
    for(auto u:toposort){ //遍历拓扑序列
        for(auto node:hparg[u]){ //遍历可以从哪里到达当前结点
            int v=node.x,w=node.y;
            dp[u]=max(dp[u],dp[v]+w); //更新最大距离
        }
        dp[u]=max(dp[u],s[u]); //记得有s数组的时间限制
    }
    for(int i=1;i<=n;i++)cout<<dp[i]<<endl;
    return 0;
}

预计得分：$100pts$
预计时间超过：$100\%$用户