UESTC 482 Charitable Exchange(스레드 트리)
Have you ever heard a star charity show called Charitable Exchange? In this show, a famous star starts with a small item which values 1 1yuan. Then, through the efforts of repeatedly exchanges which continuously increase the value of item in hand, he (she) finally brings back a valuable item and donates it to the needy.
In each exchange, one can exchange for an item of Vi yuan if he (she) has an item values more than or equal to Ri Ri yuan, with a time cost of Ti Ti minutes.
Now, you task is help the star to exchange for an item which values more than or equal to M M yuan with the minimum time.
Input
The first line of the input is T T (no more than 20 20), which stands for the number of test cases you need to solve.
For each case, two integers N N, M M ( 1≤N≤105 1≤N≤105, 1≤M≤109 1≤M≤109) in the first line indicates the number of available exchanges and the expected value of final item. Then N N lines follow, each line describes an exchange with 3 3 integers Vi Vi, Ri Ri, Ti Ti ( 1≤Ri≤Vi≤109 1≤Ri≤Vi≤109, 1≤Ti≤109 1≤Ti≤109).
Output
For every test case, you should output
Case #k:
first, where k k indicates the case number and counts from 1 1. Then output the minimum time. Output −1 −1 if no solution can be found. Sample Input
3 3 10 5 1 3 8 2 5 10 9 2 4 5 2 1 1 3 2 1 4 3 1 8 4 1 5 9 5 1 1 10 4 10 8 1 10 11 6 1 7 3 8
Sample Output
Case #1: -1 Case #2: 4 Case #3: 10
이 문제는 모든 가치의 이산화를 필요로 하고 가치는 대소 관계만 유용하며 구체적인 수치는 소용없다.이산화 후 n개의 테두리가 되고 최대 200000개의 점이 있다. 각 점의 최소 비용은 이 점에서 최대 값의 점까지 소비하는 최소 값이다. 왼쪽에서 오른쪽으로 한 번 훑어보고 최소값을 업데이트하고 물어보면 라인 트리로 유지보수한다.
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
int l,r,v,next;
}p[200005];
long long tree[300005*2];
long long inf;
void update(int rt,int l,int r,int rr,long long v)
{
if(l>rr||r<rr) return ;
if(l==rr&&r==rr)
{
tree[rt]=v;
return ;
}
int mid=(l+r)/2;
update(2*rt,l,mid,rr,v);
update(2*rt+1,mid+1,r,rr,v);
tree[rt]=min(tree[2*rt+1],tree[2*rt]);
}
long long query(int rt,int l,int r,int ll,int rr)
{
if(ll>r||rr<l) return inf;
if(ll<=l&&rr>=r) return tree[rt];
int mid=(l+r)/2;
long long ret=inf;
ret=min(ret,query(2*rt,l,mid,ll,rr));
ret=min(ret,query(2*rt+1,mid+1,r,ll,rr));
return ret;
}
int h[300005],vis[300005],a[300005],v[3][100005],cnt,r[300005];
int n,m,mx;
void add(int l,int r,int t)
{
p[++cnt].l=l; p[cnt].r=r;
p[cnt].next=h[l];h[l]=cnt;
p[cnt].v=t;
}
void spfa(int st)
{
int i,j;
for(i=1;i<=mx;i++)
{
update(1,1,mx,i,inf);
vis[i]=0;
r[i]=i;
}
update(1,1,mx,1,0);
for(i=1;i<=mx;i++)
{
int now=i;
long long mi=query(1,1,mx,i,mx);
for(j=h[now];j>0;j=p[j].next)
{
int r=p[j].r;
long long tp=query(1,1,mx,r,mx);
if(tp>mi+p[j].v)
{
update(1,1,mx,r,mi+p[j].v);
}
}
}
}
int main()
{
int T; scanf("%d",&T);
int i,j,k;
inf=1000000000;
inf*=inf;
for(int Case=1;Case<=T;Case++)
{
scanf("%d%d",&n,&m);
cnt=0;memset(h,0,sizeof(h));
map<int,int> f;
f[m]=1;
a[++cnt]=m;
a[++cnt]=1;
f[1]=1;
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&v[0][i],&v[1][i],&v[2][i]);
for(j=0;j<2;j++)
{
if(f[v[j][i]]==0)
{
f[v[j][i]]=1;
a[++cnt]=v[j][i];
}
}
}
sort(a+1,a+1+cnt);
for(i=1;i<=cnt;i++) f[a[i]]=i;
m=f[m];
mx=cnt;
cnt=0;
for(i=1;i<=n;i++)
{
add(f[v[1][i]],f[v[0][i]],v[2][i]);
}
spfa(f[1]);
long long ans=inf;
ans=query(1,1,mx,m,mx);
printf("Case #%d: ",Case);
if(ans==inf) printf("-1
");
else printf("%lld
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.