POJ 1062 dij

一道读题读的不明所以的题...

每个人只能接受和自己等级差距不超过m的人进行交易包括间接交易

所以我们可以枚举每一个长度为m的围绕着酋长的等级区间每次都对这个等级区间内的人进行操作求dis[1]

在这里的建图方式是很难得的灵光一现呢..

将0点作为源点每一个物品的本身直接购买的价值设为初始值对它们进行所给等级区间允许内的松弛操作找出其中最小的dis[1]

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<map>

#include<math.h>

#include<queue>

#include<iostream>

using namespace std;

int m,n;

int dis[105];

int a[105];

struct node

{

    int v;

    int nex;

    int w;

};

node b[30050];

int point [105];

int level[105];

bool vis[105];

int cnt;

void init()

{

    cnt=0;

    for(int i=1; i<=n; i++)

        point[i]=-1;

    for(int i=1; i<=n; i++)

        vis[i]=true;

}

void add(int u,int v,int w)

{

    b[cnt].v=v;

    b[cnt].w=w;

    b[cnt].nex=point[u];

    point[u]=cnt;

    cnt++;

}

void dij(int l,int r)

{

    for(int i=1; i<=n; i++)

    {

        int p=-1;

        int minn=999999999;

        for(int k=1; k<=n; k++)

        {

            if(vis[k]&&minn>dis[k])

            {

                minn=dis[k];

                p=k;

            }

        }

        if(p==-1)

            return ;

        vis[p]=false;

        for(int tt=point[p]; tt!=-1; tt=b[tt].nex)

        {

            int v=b[tt].v;

            int w=b[tt].w;

            if(level[v]>=l&&level[v]<=r&&level[p]>=l&&level[p]<=r&&vis[v])

            {

                if(dis[v]>w+dis[p])

                {

                    dis[v]=dis[p]+w;

                }

            }

        }

    }

}

int main()

{

    while(~scanf("%d%d",&m,&n))

    {

        init();

        for(int i=1; i<=n; i++)

        {

            int p;

            int l,x;

            scanf("%d%d%d",&p,&l,&x);

            level[i]=l;

            a[i]=p;

            for(int k=1; k<=x; k++)

            {

                int d;

                int w;

                scanf("%d%d",&d,&w);

                add(d,i,w);

            }

        }

        for(int i=1; i<=n; i++)

            dis[i]=a[i];

        int ans=999999999;

        for(int l=level[1]-m; l<=level[1]; l++)

        {

            int r=l+m;

            for(int i=1; i<=n; i++)

                vis[i]=true;

            for(int i=1; i<=n; i++)

                dis[i]=a[i];

            dij(l,r);

            if(ans>dis[1])

                ans=dis[1];

        }

        printf("%d\n",ans);

    }

}

巴特西

POJ 1062 dij

最新文章

热门文章