| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
怎么过的……帮我看看……In Reply To:N^2暴力也过。 Posted by:jsn1993 at 2009-09-26 20:03:10
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int inf=1<<30;
int n,e,t,f[90000];
struct qwq{
int l,r,c;
}ti[10050];
bool cmp(const qwq&a,const qwq&b){
return a.r<b.r;
}
bool yes=true;
int main(){
scanf("%d%d%d",&n,&e,&t);
for(int i=1;i<=n;++i){
scanf("%d%d%d",&ti[i].l ,&ti[i].r ,&ti[i].c );
if(ti[i].l <=e) yes=false;
}
sort(ti+1,ti+n+1,cmp);
if(ti[n].r <n||yes==true){//kacha
cout<<"-1"<<endl; return 0;
}
for(int i=1;i<=ti[n].r ;++i) f[i]=inf;//
f[e-1]=0;
for(int i=1;i<=n;++i){
int minn=inf;
for(int x=ti[i].l -1;x<ti[i].r ;++x){
minn=min(minn,f[x]);
}
f[ti[i].r ]=min(minn+ti[i].c ,f[ti[i].r ]);
}
int ans=inf;
for(int i=t;i<=ti[n].r ;++i) ans=min(ans,f[i]);
if(ans!=inf) cout<<ans<<endl;
else cout<<"-1"<<endl;
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator