# 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

477 篇文章43 人订阅

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

### hdu---（1325）Is It A Tree?（并查集）

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

3278

33010

### 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

### 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