Charitable Exchange

Time Limit: 20 Sec

Memory Limit: 256 MB

題目連接

http://acm.uestc.edu.cn/#/problem/show/482

Description

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$ yuan. 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 $R_i$ yuan, with a time cost of $T_i$ minutes.

Now, you task is help the star to exchange for an item which values more than or equal to $M$ yuan with the minimum time.

Input

The first line of the input is $T$ (no more than $20$), which stands for the number of test cases you need to solve.

For each case, two integers $N$, $M$ ($1 \leq N \leq 10^5$, $1 \leq M \leq 109$) in the first line indicates the number of available exchanges and the expected value of final item. Then $N$ lines follow, each line describes an exchange with $3$ integers $V_i$, $R_i$, $T_i$ ($1 \leq R_i \leq V_i \leq 10^9$, $1 \leq T_i \leq 109$).

Output

For every test case, you should output?Case #k:?first, where $k$ indicates the case number and counts from $1$. Then output the minimum time. Output $-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

HINT

?

題意

每一個(gè)物品價(jià)值為x，可以由價(jià)值為r的物品來(lái)?yè)Q，需要花費(fèi)t秒

然后問(wèn)你最小花費(fèi)多少秒能夠得到價(jià)值至少為m的物品

一開(kāi)始你有價(jià)值為1的物品

題解：

為毛我的dp+線段樹(shù)優(yōu)化t了，迷的不行

正解用優(yōu)先隊(duì)列，然后直接bfs就好了

代碼

#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> #include <map> #include <stack> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); #define sspeed ios_base::sync_with_stdio(0);cin.tie(0) #define test freopen("test.txt","r",stdin) const int maxn=202501; #define mod 1000000007 #define eps 1e-9 const int inf=0x3f3f3f3f; const ll infll = 0x3f3f3f3f3f3f3f3fLL; inline ll read() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } //**************************************************************************************struct node {ll r,v,t; }a[maxn]; bool cmp(node aa,node bb) {if(aa.r==bb.r&&aa.v==bb.v)return aa.t<bb.t;if(aa.r==bb.r)return aa.v<bb.v;return aa.r<bb.r; } struct node2 {ll x,t;bool operator<(const node2 &p1)const{return t>p1.t||t==p1.t&&x>p1.x;} }; ll ans=0; int n,m; ll bfs() {priority_queue<node2>q;node2 xx;xx.x=1;xx.t=0;q.push(xx);int B=0;int i;ll anss=-1;while(!q.empty()){xx=q.top();q.pop();if(xx.x>=m){anss=xx.t;break;}for(i=B;i<=n;i++){if(a[i].r>xx.x)break;if(a[i].r<=xx.x&&a[i].v>xx.x){node2 kk;kk.x=a[i].v;kk.t=xx.t+a[i].t;q.push(kk);}}B=i;}return anss; } int main() {int t=read();for(int cas=1;cas<=t;cas++){n=read(),m=read();for(int i=0;i<n;i++)a[i].v=read(),a[i].r=read(),a[i].t=read();sort(a,a+n,cmp);ans=0;ans=bfs();printf("Case #%d: %lld\n",cas,ans);} }

?

?

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的CDOJ 482 Charitable Exchange bfs的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。