1 条题解

  • 0
    @ 2023-10-18 9:56:06

    C++ :

    #include<bits/stdc++.h>
    using namespace std;
    const int N=50010,M=3*N+10;
    int h[N],e[M],ne[M],w[M],idx;
    bool st[N];
    int dist[N];
    int n,m;
    void add(int a,int b,int c)
    {
        e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    }
    void spfa()
    {
        queue<int> q;
        memset(dist,-0x3f,sizeof dist);
        q.push(0);
        dist[0]=0;
        st[0]=true;
        while(q.size())
        {
            int t=q.front();
            st[t]=false;
            q.pop();
            for(int i=h[t];i!=-1;i=ne[i])
            {
                int j=e[i];
                if(dist[j]<dist[t]+w[i])
                {
                    dist[j]=dist[t]+w[i];
                    if(!st[j])
                    {
                        q.push(j);
                        st[j]=true;
                    }
                }
            }
        }
    }
    int main()
    {
        cin>>n;
        memset(h,-1,sizeof h);
        for(int i=1;i<=50001;i++)
        {
            add(i-1,i,0);
            add(i,i-1,-1);
        }
        while(n--)
        {
            int a,b,c;
            cin>>a>>b>>c;
            a++,b++;
            add(a-1,b,c);
        }
        
        spfa();
        cout<<dist[50001];
        return 0;
    }
    
    • 1

    信息

    ID
    758
    时间
    1000ms
    内存
    128MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者