欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

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

本菜鸡还是太菜了,看了半天别人的题解发现理解错题目意思了,题目的等级是这样规定的如果你的等级是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

相关标签: 最短路 acm暑训