沭阳做网站的公司百度广告投放技巧

这个一道最短路题；这里难处理的就是等级只差的问题；这里我们就用枚举法；假设等级只差为L=3；酋长的等级为5，这里就只存在这几种情况2-5,3-6,4-7,5-8；我们只要处理这几种情况就可以了；至于建图就直接用钱数就可以了；

#include<cstdio>
#include<iostream>
using namespace std;
const int inf = 0x7fffffff;
int level[124],map[124][124],L,N,dis[124],hash[124];
void Empty(  )
{for( int i = 0 ; i <= N; i ++ ){for( int j = 0 ; j <= N ; j ++ )map[i][j] = inf;}    
}
int Dij()
{int LL = level[1],ans=inf;for( int i = LL -L ; i <= LL ; i ++ )//枚举所有等级只差 
   {for( int j = 1 ; j <= N ; j ++ ){dis[j] = map[0][j];hash[j] = 0;     }        hash[0] = 1;for( int j = 1; j <= N ; j ++ )//迪杰斯特拉 
        {int min = inf,t;for( int k = 1 ; k <= N ; k ++ ){if( !hash[k] && min > dis[k] && level[k] >= i && level[k] <= i + L ){//判断等级只差不能超出L min = dis[k] ; t = k;}        }hash[t] = 1;for( int k = 1 ; k <= N ; k ++ ){if( map[t][k]!= inf && !hash[k] && level[k] >= i && level[k] <= i + L)if( dis[k] > min + map[t][k] ){dis[k] = min + map[t][k];    }}} if( ans > dis[1] ) ans = dis[1];}return ans;
}
int main( )
{int n,price,num;while( scanf( "%d %d",&L , &N  )==2 ){         Empty(  );for( int i = 1 ; i <= N ; i++ ){scanf( "%d %d %d",&price,&level[i],&n );map[0][i] = price;for( int j = 0 ; j < n ; j ++ ){scanf( "%d %d",&num , &price );map[num][i] = price;         }        }printf( "%d\n",Dij() );    }return 0;    
}