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 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 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 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
",++cas,bfs());
    }
    return 0;
}
   
Case #1: -1
Case #2: 4
Case #3: 10