【UESTC 482】Charitable Exchange（优先队列+bfs）

11lxm

　　给你n个物品交换，每个交换用r,v,t描述，代表需要用r元的东西花费t时间交换得v元的东西。一开始只有1元的东西，让你求出交换到价值至少为m的最少时间代价。
相当于每个交换是一条边，时间为边权，求走到价值大于等于m的点的最短路径。
bfs的时候，用优先队列来储存状态，每次取出花费总时间最小的状态。



#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
struct node{
int r,v;
ll t;
}a[100005];
int n,m,cas;
int cmp(const node &a, const node &b){
return a.r<b.r;
}
struct cmp2{
bool operator ()(const node &a, const node &b)
{
return a.t>b.t;
}
};
priority_queue<node, vector<node>, cmp2>q;
ll bfs(){
int l=1,i;
q.push((node){0,1,0});
while(!q.empty()){
node s=q.top();
q.pop();
if(s.v>=m)
return s.t;
for(i=l;i<=n;i++){
if(s.v>=a.r&&s.v<a.v)
q.push((node){0,a.v,s.t+a.t});
if(s.v<a.r)
break;
}
l=i;
}
return -1;
}
int main(){
scanf("%d",&cas);
for(int c=1;c<=cas;c++){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&a.v,&a.r,&a.t);
while(!q.empty())q.pop();
sort(a+1,a+1+n,cmp);
printf("Case #%d: %lld\n",c,bfs());
}
return 0;
}