首先将边反向，再按 \(r\) 从大到小排序，这样可以使得答案的转移没有后效性。
令 \(ans_i\) 表示 \(i\) 这个点最少有多少资产方能无限地走下去。（初值为 \(inf\) ）
依次枚举每一条边。（令 \(u\) 为这条边的起点，\(v\) 为这条边的终点）
- 首先对现在的图进行一遍 topo ，转移方程为 \(ans_v=min(ans_v,max(r,ans_u-p))\)(要求 \(ans_u\) 不为 \(inf\)) ，因为如果只考虑当前这条边的话，\(v\) 点的资产至少要为 \(r\) 才能走出去，而且必须要使走过这条边后的资产 \(\ge ans_u\) ，于是有了上面的方程。走过的边都要删掉。
- 更新 \(ans_u=min(ans_u,r)\) ，删掉这条边，若点 \(u\) 入度为 \(0\) 则加入队列。
手动模拟一下这个过程，可以发现一个环的答案只会对后面的点有贡献，因此可以求出答案为 \(-1\) 的点。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,inf=1e18;
int n,m,ans[N],d[N];
struct edge{
int u,v,r,p;
edge(){}
edge(int u,int v,int r,int p):u(u),v(v),r(r),p(p){}
}e[N];
bool vis[N];
vector<int> g[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for (int i=1;i<=m;i++)
{
int u,v,r,p;
cin>>u>>v>>r>>p;
e[i]=edge(u,v,r,p);
}
for (int i=1;i<=n;i++) ans[i]=inf;
sort(e+1,e+1+m,[&](edge a,edge b){return a.r>b.r;});
for (int i=1;i<=m;i++) g[e[i].v].emplace_back(i),d[e[i].u]++;
queue<int> q;
for (int i=1;i<=n;i++) if (!d[i]) q.push(i);
for (int i=1;i<=m;i++)
{
while (!q.empty())
{
int u=q.front();
q.pop();
for (int nex:g[u])
{
if (vis[nex]) continue;
vis[nex]=1;
int v=e[nex].u;
d[v]--;
if (ans[u]!=inf) ans[v]=min(ans[v],max(e[nex].r,ans[u]-e[nex].p));
if (!d[v]) q.push(v);
}
}
if (vis[i]) continue;
auto& [u,v,r,p]=e[i];
vis[i]=1;
d[u]--;
ans[u]=min(ans[u],e[i].r);
if (!d[u]) q.push(u);
}
for (int i=1;i<=n;i++) cout<<(ans[i]==inf?-1:ans[i])<<' ';
}
最难的部分在于想到从大到小贪心。