思路是差分约束+前缀优化建图 跑最长路 虽然权有正有负 但是是拓扑图 可以直接跑

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+5;
int n,m,a[N],b[N],s[N],t[N],vis[N],node,dis[N];
vector<int>suf[N],vec[N];
vector<pair<int,int>>g[N];
int my(int x,int y){
    return s[x]>s[y];
}
void dfs(int u){
    if(vis[u]){
        return;
    }
    vis[u]=1;
    for(auto [v,w]:g[u]){
        dis[v]=max(dis[v],dis[u]+w),dfs(v);
    }
}
signed main(){
    cin>>n>>n>>dis[1];
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>s[i]>>t[i],vec[a[i]].push_back(i);
    }
    node=n;
    for(int i=1;i<N;i++){
        sort(vec[i].begin(),vec[i].end(),my);
        int flag=0;
        for(int j=0;j<vec[i].size();j++){
            node++,suf[i].push_back(node);
            if(!flag){
                g[node].push_back({vec[i][j],-s[vec[i][j]]});
            }
            else{
                g[node].push_back({node-1,0}),g[node].push_back({vec[i][j],-s[vec[i][j]]});
            }
            flag=1;
        }
    }
    for(int i=1;i<=n;i++){
        if(vec[b[i]].size()){
            int l=0,r=vec[b[i]].size()-1,ret=-1;
            while(l<=r){
                int mid=(l+r)>>1;
                if(t[i]<=s[vec[b[i]][mid]]){
                    ret=mid,l=mid+1;
                }
                else{
                    r=mid-1;
                }
            }
            if(ret==-1){
                continue;
            }
            g[i].push_back({suf[b[i]][ret],t[i]});
        }
    }
    for(int i=1;i<=node;i++){
        g[0].push_back({i,dis[i]});
    }
    for(int i=1;i<=n;i++){
        dis[i]=-1e18;
    }
    dfs(0);
    for(int i=2;i<=n;i++){
        cout<<dis[i]<<' ';
    }
}