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

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

代码语言：javascript复制

#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[i].r&&s.v<a[i].v)
                q.push((node){0,a[i].v,s.t a[i].t});
            if(s.v<a[i].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[i].v,&a[i].r,&a[i].t);
 
        while(!q.empty())q.pop();
        sort(a 1,a 1 n,cmp);
 
        printf("Case #%d: %lldn",c,bfs());
    }
    return 0;
}

队列

0 人点赞