M - 昂贵的聘礼(超级源点加dij)

本菜鸡还是太菜了，看了半天别人的题解发现理解错题目意思了，题目的等级是这样规定的如果你的等级是x，最大差值k,那么你可以交易的人的等级就在【x-k,x+k】之间，其他等级都不可以，然后因为你没有等级限制，那么就特别难搞，我们就枚举假设和我们交换的人的最低等级，但是最低等级+m要包含酋长的等级所以最低等级就是在[rank[1]-m,rank[1]];
然后就是代码了

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#include<deque>
#include<map>
#include<stdlib.h>
#include<set>
#include<iomanip>
#include<stack>
#define ll long long
#define ms(a,b) memset(a,b,sizeof(a))
#define lowbit(x) x & -x
#define fi first
#define se second
#define bug cout<<"----acac----"<<endl
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
using namespace std;
const int maxn = 1e5 + 50;
const int maxm = 1.5e5+50;
const double eps = 1e-7;
const double inf = 0x3f3f3f3f;
const ll  lnf  = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const  double pi=3.141592653589;
int rank1[105],dis[105],vis[105],head[105];
int n,m,cnt;
struct node
{
    int to,val,next;
}a[100005];
void add(int u,int v,int val)
{
    a[cnt].to=v;
    a[cnt].val=val;
    a[cnt].next=head[u];
    head[u]=cnt++;
}
struct point
{
    int id,val;
    point(int id,int val)
    {
        this->id=id;
        this->val=val;
    }
    bool operator<(const point &x)const
    {
        return val>x.val;
    }
};
void dij(int s,int k)
{
    for(int i=0;i<=n;i++)
    {
        dis[i]=inf;
        vis[i]=0;
    }
    priority_queue<point>q;
    dis[s]=0;
    q.push(point(s,0));
    while(!q.empty())
    {
        int u=q.top().id;
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];~i;i=a[i].next)
        {
            int v=a[i].to;
            int w=a[i].val;
            if(rank1[v]<k||rank1[v]-k>m)continue;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                q.push(point(v,dis[v]));
            }
        }
    }
}
int main()
{
    cnt=0;
    ms(head,-1);
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        int w,r,k;
        scanf("%d%d%d",&w,&r,&k);
        rank1[i]=r;
        add(0,i,w);
        for(int j=1;j<=k;j++)
        {
            int v,x;
            scanf("%d%d",&v,&x);
            add(v,i,x);
        }
    }
    int ans=inf;
    for(int i=rank1[1]-m;i<=rank1[1];i++)
    {
        dij(0,i);
        ans=min(ans,dis[1]);
    }
    printf("%d\n",ans);
    return 0;
}

本文地址：https://blog.csdn.net/qcccc_/article/details/107506860