ABC368E

建图后因为是拓扑跑了dij 但是有WA 换成spfa就不会有WA了 但是有T

#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 dij(int s){
    priority_queue<pair<int,int>>q;
    q.push({0,s});
    while(!q.empty()){
        auto [w,u]=q.top();
        q.pop();
        if(!vis[u]){
            vis[u]=1,dis[u]=w;
            for(auto [v,ww]:g[u]){
                if(!vis[v]){
                    q.push({w+ww,v});
                }
            }
        }
    }
    for(int i=2;i<=n;i++){
        cout<<dis[i]<<" ";
    }
}
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]});
    }
    dij(0);
}