学步园

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 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 <= 10^5, 1 <= M <= 10^9) 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 <= 10^9, 1 <= Ti <= 10^9).

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

//第一次用优先队列 ~~嘎嘎~~
//还是边理解别人的代码边打的
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;

#define N 1000000
long m,coun;

struct Stu
{
	long long v,u,t;
};
Stu stu[N];

struct Node
{
	long long t;
	long long money;
	friend bool operator<(Node a,Node b)
	{
		return a.t > b.t;
	}
};

long long cmp(Stu a, Stu b)
{
	return a.u < b.u;
}
long long bfs()
{
	Node front,rear;
	long long left = 1,i;
	front.money = 1,front.t = 0;
	priority_queue<Node> q;
	q.push(front);
	while(!q.empty())
	{
		rear = q.top();
		q.pop();
		if(rear.money >= m)
			return rear.t;
		for(i = left; i <= coun; i++)
		{
			if(rear.money>=stu[i].u&&stu[i].v>rear.money)
			{
				front.money=stu[i].v;
				front.t=rear.t+stu[i].t;
				q.push(front);
			}
			if(rear.money<stu[i].u)
				break;
		}
		left = i;
	}
	return -1;
}

int main()
{
	long long T;
	scanf("%lld", &T);
	for(long long t = 1; t <= T; t++)
	{
		long long n;
		coun = 0;
		scanf("%lld%lld",&n, &m);
		for(long long i = 1; i <= n; i++)
		{
			long long a,b,c;
			scanf("%lld%lld%lld", &a,&b,&c);
			if(b == a)
				continue;
			coun++;
			stu[coun].v = a,stu[coun].u = b,stu[coun].t = c;
		}
		sort(stu+1, stu+1+coun, cmp);
		long long end = bfs();
		printf("Case #%lld: %lld\n",t,end);
	}
}