poj1201

发表于 | 分类于 | 阅读数 次

链接:poj1201

题解

  • 板子题，点上区间问题转为前缀和的点上问题，就可以建图了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
const int N=1e5+7;
const int inf=0x3f3f3f3f;
using namespace std;
int n,m,cnt,mx,mn,nxt[N],w[N],to[N],head[N],dis[N],inq[N];
inline void adde(int a,int b,int c){
	w[++cnt]=c;
	to[cnt]=b;
	nxt[cnt]=head[a];
	head[a]=cnt;
}
queue<int>q;
void spfa(){
	q.push(mn);
	inq[mn]++;dis[mn]=0;
	while(!q.empty()){
		int k=q.front();
		q.pop();inq[k]--;
		for(int i=head[k],v;i;i=nxt[i]){
			if(dis[v=to[i]]>=dis[k]+w[i])continue;
			dis[v]=dis[k]+w[i];
			if(!inq[v]){q.push(v);inq[v]++;}
		}
	}
}
int main(){
	while(~scanf("%d",&n)){
		mx=0;mn=inf;
		memset(head,0,sizeof head);
		memset(dis,0,sizeof dis);
		rep(i,1,n){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			mx=max(mx,b);
			mn=min(mn,a);
			adde(a-1,b,c);
		}
		rep(i,mn,mx)adde(i-1,i,0),adde(i,i-1,-1),dis[i]=-inf;
		spfa();
		printf("%d\n",dis[mx]);
	}
	return 0;
}