POJ1201.md

差分约束跑最长路，dist就是前缀和，考虑建边： 1.每次输入[a,b]和c，a-1向b建边，长度为c (sum[b]-sum[a-1]>=c) 2.i向i+1连边，边权为0 (sum[i+1]-sum[i]>=0) 3.i+1向i连边，边权为-1 (sum[i+1]-sum[i]<=1)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN = 1e5+7;
struct Graph{
    int head[MAXN],to[MAXN<<2],nxt[MAXN<<2],cst[MAXN<<2],tot;
    Graph(){ memset(head,255,sizeof(head)); tot = 0; }
    void ADDEDGE(int u, int v, int c){
        tot++;
        to[tot] = v;
        cst[tot] = c;
        nxt[tot] = head[u];
        head[u] = tot;
    }
}G;
int n;
bool vis[MAXN];
int sum[MAXN];
void SPFA(){
    memset(vis,false,sizeof(vis));
    memset(sum,255,sizeof(sum));
    deque<int> que;
    sum[0] = 0;
    que.push_front(0);
    while(!que.empty()){
        int u = que.front();
        que.pop_front();
        vis[u] = false;
        for(int i = G.head[u]; ~i; i = G.nxt[i]){
            int v = G.to[i];
            int c = G.cst[i];
            if(sum[v]<sum[u]+c){
                sum[v] = sum[u] + c;
                if(!vis[v]){
                    if(!que.empty()&&sum[v]<sum[que.front()]) que.push_back(v);
                    else que.push_front(v);
                    vis[v] = true;
                }
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    int maxl = 0;
    for(int i = 1; i <= n; i++){
        int l, r, p;
        scanf("%d %d %d",&l,&r,&p);
        maxl = max(maxl,r+1);
        G.ADDEDGE(l,r+1,p);
    }
    for(int i = 0; i < maxl; i++) G.ADDEDGE(i,i+1,0), G.ADDEDGE(i+1,i,-1);
    SPFA();
    printf("%d\n",sum[maxl]);
    return 0;
}