Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

怎么过的……帮我看看……

Posted by 896295334 at 2017-09-09 16:17:52 on Problem 3171
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator