poj1062

这个题目我最开始看题目看了半天，看不懂。。但是通过看样例及答案终于看懂了。。。

首先先解决等级的关系。。如果等级越界，则不能交换。。所以原本等级的界限是

[rank[1]-m,rank[1]+m],但是这个边界里面会出现等级只差大于m，所以等级的区间应该是

[rank[1]-m,rank[1]],[rank[1]-m+1,rank[1]+1]............等等，所以一直枚举到 [rank[1],rank[1]+m]..所以先通过枚举得到可以交换的点。。然后就是题目的意思了。。。

我理解的优惠相当于是分解。。。比如如果得到1号物品需要得到2号物品和8000金币。不就相当于1号到2号号为单向路劲，权值为8000.。。求各个点到1号点的最短路加上这个点的价值。。如图所示。。。

                1(10000)---------->2(1000)--------->4(50)

                 |              8000                  200    |

                 |--------------------->3(3000)----------|

                    5000                             200

画图之后一目了然。。。然后运用dijkstra解决。。。。。。。

希望各位指正我的想法。。

代码如下：

#include<cstdio>
#include<cstring>
#define INF 0x3f3f3f3f
const int maxn=100+10;
int m,n;
int vis[maxn],dis[maxn],e[maxn][maxn];
int withtin[maxn],value[maxn],ranki[maxn];

int dijkstra()
{
    int tmp,now,i,j;
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    for(i=1;i<=n;i++)
    {
        tmp=INF;
        for(j=1;j<=n;j++)
        {
            if(!vis[j]&&withtin[j]&&dis[j]<tmp)
            {
                tmp=dis[j];
                now=j;
            }
        }
        vis[now]=1;
        for(j=1;j<=n;j++)
        {
            if(!vis[j]&&withtin[j]&&dis[j]>dis[now]+e[now][j])
                dis[j]=dis[now]+e[now][j];
        }
    }
    tmp=INF;
    for(i=1;i<=n;i++)
    {
        if(dis[i]+value[i]<tmp)
            tmp=dis[i]+value[i];
    }
    return tmp;
}


int main()
{
    int i,j,t,cost;
    int p,l,x,val,min_cost;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(e,0x3f,sizeof(e));
        for(i=1;i<=n;i++)
             for(j=1;j<=n;j++)
            {
                if(i==j)
                e[i][j]=0;
            }
        for(i=1;i<=n;i++)
        {
            scanf("%d%d%d",&value[i],&ranki[i],&x);
            for(j=1;j<=x;j++)
            {
                scanf("%d%d",&t,&val);
                e[i][t]=val;
            }
        }
        min_cost=INF;
        for(i=0;i<=m;i++)
        {
            memset(withtin,0,sizeof(withtin));
            for(j=1;j<=n;j++)
            {
                if(ranki[j]>=ranki[1]-m+i&&ranki[j]<=ranki[1]+i)
                    withtin[j]=1;
            }
            cost=dijkstra();
             if(cost<min_cost)
                min_cost=cost;
        }
        printf("%d\n",min_cost);
    }
}

poj1062,布布扣,bubuko.com

poj1062

原文：http://blog.csdn.net/u014303647/article/details/25350011