如果一个点的出度为 $0$，那么这个点的答案就被确定了，需要用它去更新别的点的答案。

我们此时删掉这个点，即删掉指向它的所有边 $(u,v)$，同时更新起点 $u$ 处的答案。

$$ans_u = min(ans_u, max(r_i, ans_v - p_i))$$

这个过程中可能产生新的出度为 $0$ 的点，我们将重复这一过程，就像拓扑排序一样。

这一过程停止后，剩余的点都拥有出度。

因为 $p_i \geq 0$，所以若初始资产等于剩余 $r_i$ 中的最大值，那么一定可以不停游走。

于是我们考虑按照 $r_i$ 从大到小删边 $(u,v)$。

我们每一次删掉的边都是当前剩余的 $r_i$ 中最大的，所以一定可以不停游走，故更新 $u$ 的答案 $ans_u = min(ans_u, r_i)$。

这个过程中如果产生了出度为 $0$ 的点，那么我们重复上面删点的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5;
struct Edge{int u,v,r,p,id;};
int n,m;
Edge E[maxn+5];
vector<Edge> V[maxn+5];
int dg[maxn+5];
bool vis[maxn+5];
int ans[maxn+5];
queue<int> qu;
inline bool Cmp(Edge x,Edge y){return x.r>y.r;}
signed main(){
    int u,v,r,p,id;
    memset(ans,0x7f,sizeof(ans));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&u,&v,&r,&p);
        E[i].u=u,E[i].v=v,E[i].r=r,E[i].p=p,E[i].id=i;
        V[v].push_back(E[i]);
        dg[u]++;
    }
    sort(E+1,E+m+1,Cmp);
    for(int i=1;i<=n;i++) if(!dg[i]) qu.push(i);
    for(int i=1;i<=m;i++){
        while(qu.size()){
            u=qu.front(),qu.pop();
            for(Edge j:V[u]){
                v=j.u,r=j.r,p=j.p,id=j.id;
                if(vis[id]) continue;
                if(ans[u]!=ans[0])
                    ans[v]=min(ans[v],max(r,ans[u]-p));
                dg[v]--,vis[id]=1;
                if(!dg[v]) qu.push(v);
            }
        }
        u=E[i].u,v=E[i].v,r=E[i].r,p=E[i].p,id=E[i].id;
        if(vis[id]) continue;
        ans[u]=min(ans[u],r);
        dg[u]--;
        vis[id]=1;
        if(dg[u]) continue;
        qu.push(u);
    }
    for(int i=1;i<=n;i++){
        if(ans[i]==ans[0]) printf("-1 ");
        else printf("%d ",ans[i]);
    }
    return 0;
}