UESTC 482 Charitable Exchange(优先队列+bfs)

Charitable Exchange

Time Limit: 4000/2000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit Status

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 Ri yuan, with a time cost of Ti 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≤N≤105, 1≤M≤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 Vi, Ri, Ti (1≤Ri≤Vi≤109, 1≤Ti≤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 and output

Sample Input

Sample Output

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 优先队列 贪心+bfs #include <iostream> #include <string.h> #include <stdlib.h> #include <algorithm> #include <math.h> #include <stdio.h> #include <queue> using namespace std; #define MAX 100000 struct Node { long long int v; long long int r; long long int t; }a[MAX+5]; struct node { long long int value; long long int time; bool friend operator <(node a,node b) { return a.time>b.time; } }; priority_queue<node> q; int n,m; int right1; int cmp(Node a,Node b) { return a.r<b.r; } long long int bfs() { node term1; term1.value=1;term1.time=0; q.push(term1); int left=1,i; while(!q.empty()) { node term2=q.top(); q.pop(); if(term2.value>=m) { return term2.time; } for(i=left;i<=right1;i++) { if(term2.value>=a[i].r&&term2.value<a[i].v) { node temp; temp.value=a[i].v; temp.time=term2.time+a[i].t; q.push(temp); } if(term2.value<a[i].r) break; } left=i; } return -1; } int main() { int t; int cas=0; scanf("%d",&t); long long int vv,rr,tt; while(t--) { scanf("%d%d",&n,&m); right1=0; for(int i=1;i<=n;i++) { scanf("%lld%lld%lld",&vv,&rr,&tt); if(vv==rr) continue; a[++right1].v=vv;a[right1].r=rr;a[right1].t=tt; } while(!q.empty()) q.pop(); sort(a+1,a+1+right1,cmp); printf("Case #%d: %lld\n",++cas,bfs()); } return 0; }

Case #1: -1 Case #2: 4 Case #3: 10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

POJ-2329 Nearest number - 2(BFS)

Nearest number - 2 Time Limit: 5000MS Memory Limit: 65536K Total Submis...

2474
来自专栏算法修养

ZOJ 3537 Cake(凸包判定+区间DP)

Cake Time Limit: 1 Second Memory Limit: 32768 KB You want to hold a par...

3769
来自专栏ml

hdu---(1325)Is It A Tree?(并查集)

Is It A Tree? Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/3276...

3278
来自专栏小樱的经验随笔

HDU 2034 人见人爱A-B

人见人爱A-B Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (J...

33010
来自专栏ml

HDUOJ---1867 A + B for you again

A + B for you again Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 3276...

3596
来自专栏函数式编程语言及工具

Scalaz(55)- scalaz-stream: fs2-基础介绍,fs2 stream transformation

    fs2是scalaz-stream的最新版本,沿用了scalaz-stream被动式(pull model)数据流原理但采用了全新的实现方法。fs2比较...

2416
来自专栏算法修养

PAT 甲级 1104 sum of Number Segments

1104. Sum of Number Segments (20) 时间限制 200 ms 内存限制 65536 kB 代码长度限制 16...

2835
来自专栏算法修养

HOJ 2985 Wavio Sequence(最长递增子序列以及其O(n*logn)算法)

Wavio Sequence My Tags (Edit) Source : UVA Time limit : 1 sec Memor...

2816
来自专栏HansBug's Lab

2751: [HAOI2012]容易题(easy)

2751: [HAOI2012]容易题(easy) Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 1087 ...

2235
来自专栏算法修养

CodeForces 666B World Tour(spfa+枚举)

B. World Tour time limit per test 5 seconds memory limit per test 512 mega...

3384

扫码关注云+社区

领取腾讯云代金券