枚举+最短路 poj1062

这里有个非常坑的地方，还有比酋长地位还更高的人，我也是看了论坛才知道。。。

在这里我把编号1看成终点，优惠价格看成相应的替代品编号到可替代品编号的权值，比如说有了2再加8000就到了1，那么2到1的弧长权值就是8000，dis[i]表示到编号i花费的最小金币数，初始的dis[i]都是物品本身价格，这里还有一个等级限制，我也看了下论坛，主要是枚举长度为m的所有区间，在每一个区间里都求一次最短路，求最小的值作为答案。

以下是我的代码，偷了懒，时间复杂度比较高：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f
int map[105][105];
int n,m,k,t,ans,cnt;
int dis[105],dis1[105],rank[105];
struct node{
    int u,v,w;
}edge[10005];
void find(int a,int b)//现在我找在区间[a,b]之间的最短路 
{
    for(int i=1;i<=n;i++)    //把初始dis复制一份，因为求最短路会改变dis的数据 
    dis1[i]=dis[i];
    for(int i=1;i<n;i++)    //n-1次循环 
    {
        for(int j=0;j<cnt;j++)    //遍历所有边 
        {
            int u=edge[j].u;
            int v=edge[j].v;
            int w=edge[j].w;
            if(rank[u]>=a&&rank[u]<=b&&rank[v]>=a&&rank[v]<=b&&dis1[v]>dis1[u]+w)//选择编号在区间里的物品 
            {
                dis1[v]=dis1[u]+w;
                if(v==1)
                {
                    ans=min(ans,dis1[v]);
                }
            }
        }
    }
}
int main()
{
    while(cin>>m>>n)
    {
        cnt=0;
        int max1=0,min1=inf;
        for(int i=1;i<=n;i++)
        {
            cin>>dis[i]>>rank[i]>>k;
            if(rank[i]>max1)
            max1=rank[i];
            if(min1>rank[i])
            min1=rank[i];
            
            for(int j=0;j<k;j++)
            {
                int u,w,v;
                cin>>u>>w;
                edge[cnt].u=u;
                edge[cnt].v=i;
                edge[cnt].w=w;
                cnt++;
            }
        }
        ans=dis[1];
        for(int i=min1;i<=max1;i++)
        {
            int j=min(i+m,max1);
            if(rank[1]>=i&&rank[1]<=j)//rank[1]一定要在区间里 
            find(i,j);
        }
        cout<<ans<<endl;
    }
    return 0;
}