制作不易望点赞收藏加关注~~~，以便不时之需

题目连接：903. 昂贵的聘礼 - AcWing题库

解题思路：虚拟一个物品0，然后反向建边，边权为物品0到物品i所花费的价格，以及物品i换物品j所省下的钱，然后枚举地位dijkstra求min

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 110
#define inf 0x3f3f3f3f

// c++ 中 rank 也是关键字 emmmmm

struct Node{
    int to,len;
    bool operator<(const Node &b)const{
        return len>b.len;
    }
};

int n,m;
int dis[N],level[N];
bool vis[N];
vector<Node> g[N];

// 对地位进行最短路
int dijkstra(int down,int up){
    memset(dis,inf,sizeof dis);
    memset(vis,false,sizeof vis);
    // 添加一个为0的点作为起点
    dis[0]=0;
    priority_queue<Node> pq;
    pq.push({0,0});
    while(!pq.empty()){
        Node now=pq.top();pq.pop();
        if(vis[now.to])continue;
        // 枚举到 1 提前退出就好
        if(now.to==1)break;
        vis[now.to]=true;
        
        for(auto [to,len]:g[now.to]){
            if(vis[to])continue;
            // 判断是否符合地位差距
            if(level[to]>=down&&level[to]<=up&&dis[to]>dis[now.to]+len){
                dis[to]=dis[now.to]+len;
                pq.push({to,dis[to]});
            }
        }
    }
    
    return dis[1];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        // 给虚拟点进行建边 权值为价格
        g[0].push_back({i,u});
        level[i]=v;
        while(w--){
            int j,k;
            cin>>j>>k;
            // 建立取代物到物品的边 权值为便宜的价格
            g[j].push_back({i,k});
        }
    }
    
    // 对所有符合 level 的范围进行枚举
    int ans=inf;
    for(int i=level[1]-m;i<=level[1];i++)ans=min(ans,dijkstra(i,i+m));
    
    cout<<ans<<endl;
    
    
    return 0;
}