POJ1602 昂贵的聘礼

卡了好几天终于过了，就是有个地方，卡限制等级的，然后就可以枚举区间SPFA，这个区间必须包涵酋长的等级，维护一个最小值，也看了别人的代码，揣测了好久，终于懂了，然后来写一次就A了，加个油。
  1 #include <iostream>
  2 #include <queue>
  3 #include <stdio.h>
  4 #include <string.h>
  5 #include <algorithm>
  6 #include <cmath>
  7 #define  INF 0xffffff
  8 #define  maxn 120
  9 #define  aabs(x) (x)>0?(x):-(x)
 10 using namespace std;
 11 
 12 int inq[maxn];
 13 int gird[maxn][maxn];
 14 int dist[maxn];
 15 int value[maxn];
 16 int level[maxn];
 17 int sign[maxn][maxn];
 18 int v[maxn][maxn];
 19 int constlevel;     //qiuzhang's level
 20 int m,n;
 21 queue<int>Q;
 22 
 23 void set(int left,int right)
 24 {
 25     int i,j;
 26     memset(v,0,sizeof(v));
 27     for(i=1;i<=n;++i)
 28     {
 29         for(j=1;j<=n;++j)
 30         {
 31             if(gird[i][j]!=INF){
 32             if( level[i]<left || level[i]>right || level[j]<left || level[j]>right )
 33                 v[i][j]=0;
 34             else
 35                 v[i][j]=1;
 36             }
 37         }
 38     }
 39     return ;
 40 }
 41 
 42 void init_for_spfa()
 43 {
 44     while(Q.size()>0)
 45         Q.pop();
 46     memset(inq,0,sizeof(inq));
 47     for(int i=2;i<=n;++i)
 48     {
 49         dist[i]=INF;
 50     }
 51     dist[1]=0;
 52     return ;
 53 }
 54 
 55 
 56 int spfa()
 57 {
 58     int i,j;
 59     int u,vv;
 60     init_for_spfa();
 61     Q.push(1);  inq[1]=1;
 62     while(Q.size()>0)
 63     {
 64         u=Q.front();    Q.pop();    inq[u]=0;
 65         for(i=1;i<=n;++i)
 66         {
 67             if(v[u][i]==0)
 68                 continue;
 69 
 70             vv=i;
 71             if(dist[vv]>dist[u]+gird[u][vv])
 72             {
 73                 dist[vv]=dist[u]+gird[u][vv];
 74                 if(inq[vv]==0)
 75                 {
 76                     Q.push(vv);  inq[vv]=1;
 77                 }
 78             }
 79         }
 80     }
 81     for(i=1;i<=n;++i)
 82         dist[i]+=value[i];
 83     dist[0]=INF;
 84     sort(dist,dist+n+1);
 85     return dist[0];
 86 }
 87 
 88 int main()
 89 {
 90     int i,j;
 91     int P,L,X,T,V;
 92     int res;
 93     int temp;
 94     while(~scanf("%d%d",&m,&n))
 95     {
 96         for(i=1;i<=n;++i)
 97             for(j=1;j<=n;++j)
 98                 gird[i][j]=INF;
 99         for(i=1;i<=n;++i)
100         {
101             scanf("%d%d%d",&P,&L,&X);
102             value[i]=P;
103             level[i]=L;
104             for(j=1;j<=X;++j)
105             {
106                 scanf("%d%d",&T,&V);
107                 gird[i][T]=V;
108             }
109         }
110         constlevel=level[1];
111         res=INF;
112         for(i=0;i<=m;++i)
113         {
114             set(constlevel-i,constlevel-i+m);
115             temp=spfa();
116             if(temp<res)
117                 res=temp;
118         }
119         printf("%d\n",res);
120     }
121     return 0;
122 }