C++14(g++5.4) 解法, 执行用时: 93ms, 内存消耗: 4460K, 提交时间: 2020-01-02 16:18:35

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5e4+2;
// b - a >= c => a <= b - c
// a <= (a + 1) 
// (a+1) <= a + 1;

// 最长路求最小值 
// b - a >= c
// (a+1) - a >= 0
// a - (a+1) >= -1
// add_edge(a, b, c);
typedef pair<int, int> pii;
int N;
vector<pii> G[MAXN];
int dis[MAXN];
bool inq[MAXN];
int inqCnt[MAXN];
int spfa() {
  memset(dis, 0x8f, sizeof(dis));
  // for (int i = 0; i <= N; i++) dis[i] = -0x3f3f3f3f;
  queue<int> Q;
  dis[0] = 0;
  Q.push(0);
  inq[0] = true;
  inqCnt[0]++;
  while (!Q.empty()) {
    int s = Q.front(); Q.pop();
    inq[s] = false;
    // cout << "Pop: " << s << " " << dis[s] << endl;
    for (auto it: G[s]) {
      int t = it.first, w = it.second;
      if (dis[t] < dis[s] + w) {
        dis[t] = dis[s] + w;
        if (inq[t]) continue;
        if (++inqCnt[t] >= N) return -1;
        inq[t] = true;
        Q.push(t);
        // cout << "Push " << t << " " << dis[t] << endl; } 
      }
    }
  }
  return dis[N];
}
int main() {
  int n; cin >> n;
  while (n--) {
    int a, b, c; cin >> a >> b >> c;
    b++;
    G[a].push_back({b, c});
    N = max(N, b);
  }
  for (int i = 0; i < N; i++) G[i].push_back({i+1, 0});
  for (int i = 0; i < N; i++) G[i+1].push_back({i, -1});
  cout << spfa() << endl;
}

C++(clang++11) 解法, 执行用时: 35ms, 内存消耗: 4216K, 提交时间: 2020-12-02 08:45:21

#include<bits/stdc++.h>
#define epb emplace_back
#define ep emplace
#define mp make_pair
#define pii pair<int,int>
#define v second
#define w first
using namespace std;
const int nn=51201;
bool in[nn];
int n,mab,a,b,c,u,dist[nn];
vector<pii>to[nn];
queue<int>q;
int main(){
	memset(dist,128,sizeof dist),
	dist[0]=0,scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d%d%d",&a,&b,&c),
		mab=max(mab,++b),
		to[a].epb(mp(c,b));
	for(int i=0;i<mab;i++)
		to[i].epb(mp(0,i+1)),
		to[i+1].epb(mp(-1,i));
	for(q.ep(0);!q.empty();q.pop()){
		u=q.front(),in[u]=false;
		for(pii i:to[u])
			if(dist[u]+i.w>dist[i.v]){
				dist[i.v]=dist[u]+i.w;
				if(!in[i.v])q.ep(i.v);
			}
	}printf("%d\n",dist[mab]);
	return 0;
}