1 条题解
-
0
#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #define ll long long using namespace std; const int INF=0x3f3f3f3f,MAXX=100000; int delta=10; int n,l,r; int cnt; int dp[MAXX+5]; struct tree{int l,r,minn;}tree[MAXX*8+5]; struct node{int l,r,v;}t[MAXX+5]; bool cmp(node x,node y){return x.r<y.r;} void Build(int k,int l,int r) { tree[k].l=l;tree[k].r=r;tree[k].minn=INF; if(l==r){return;} int mid=(l+r)>>1; Build(k<<1,l,mid); Build(k<<1|1,mid+1,r); } void add(int k,int x,int v) { if(x<tree[k].l||x>tree[k].r)return; tree[k].minn=min(tree[k].minn,v); int mid=(tree[k].l+tree[k].r)>>1; add(k<<1,x,v);add(k<<1|1,x,v); } int ask(int k,int l,int r) { int ans=INF; if(l<=tree[k].l&&r>=tree[k].r)return tree[k].minn; int mid=(tree[k].l+tree[k].r)>>1; if(l<=mid)ans=min(ans,ask(k<<1,l,r)); if(r>mid)ans=min(ans,ask(k<<1|1,l,r)); return ans; } int main() { Build(1,1,100000); scanf("%d %d %d",&n,&l,&r); l+=10;r+=10; for(int i=1;i<=n;i++) { int x,y,z; scanf("%d %d %d",&x,&y,&z); x+=10;y+=10; if(x<l)x=l;if(y>r)y=r; if(x>y)continue; t[++cnt].l=x;t[cnt].r=y;t[cnt].v=z; } sort(t+1,t+cnt+1,cmp); memset(dp,0x3f,sizeof(dp)); dp[l]=0; add(1,l,0); for(int i=1;i<=cnt;i++) { int k=INF; k=min(k,ask(1,t[i].l-1,t[i].r)); dp[t[i].r]=min(dp[t[i].r],k+t[i].v); add(1,t[i].r,dp[t[i].r]); } if(dp[r]==INF)printf("-1"); else printf("%d",dp[r]); return 0; }
- 1
信息
- ID
- 1672
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 3
- 已通过
- 3
- 上传者