区间

AcWing-362-区间

分析

见《进阶指南》第394页。

实现

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 50010;
struct edge {
    int to, next, w;
};
edge e[3 * N];
int idx, head[N];
struct node {
    int idx, dis;
    bool operator < (const node& o) const {
        return dis > o.dis;
    }
};
int n;
int dis[N];
bool mark[N];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
int spfa (int s) { // 最长路
    memset(dis, -0x3f, sizeof(dis));
    
    queue<int> q;
    dis[s] = 0;
    q.push(s);
    mark[s] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        mark[cur] = false;
        for (int i = head[cur]; i != -1; i = e[i].next) {
            int to = e[i].to, w = e[i].w;
            if (dis[cur] + w > dis[to]) {
                dis[to] = dis[cur] + w;
                if (mark[to] == false) {
                    q.push(to);
                    mark[to] = true;
                }
            }
        }
    }
    return dis[50001];
}

int main () {
    memset(head, -1, sizeof(head));
    cin >> n;
    for (int i = 1, a, b, c; i <= n; ++ i) {
        cin >> a >> b >> c;
        ++ a, ++ b;
        add_edge(a - 1, b, c);
    }
    for (int i = 1; i <= 50001; ++ i) {
        add_edge(i - 1, i, 0);
        add_edge(i, i - 1, -1);
    }
    cout << spfa(0) << endl;
    return 0;
}