|
解题思路：先建好图，注意是 有向图 ，然后以 1 点 为源点，枚举等级的限制，即每次都用spfa 求得1点 到 其他能够到达的点（由于等级的限制，在一次spfa中可能并不是所有的点都能够到达），最后求出所需最小费用。
Ps：此题中点1的等级 可能不是最高的。
请看代码：
#include
#include
#include
#include
#include
#include
#include
#include
#define mem(a , b) memset(a , b , sizeof(a))
using namespace std ;
inline void RD(int &a)
{
a = 0 ;
char t ;
do
{
t = getchar() ;
}
while (t < '0' || t > '9') ;
a = t - '0' ;
while ((t = getchar()) >= '0' && t <= '9')
{
a = a * 10 + t - '0' ;
}
}
inline void OT(int a)
{
if(a >= 10)
{
OT(a / 10) ;
}
putchar(a % 10 + '0') ;
}
const int MAXN = 105 ;
const int INF = 0x7fffffff ;
int m , n ;
struct Node
{
int adj ;
int c ;
};
vector vert[MAXN] ;
int P[MAXN] ; // 每个物品的价格
int L[MAXN] ; // 每个物品持有者的等级
int d[MAXN] ; // 记录每次 点 1 到其他点的最短路径
void clr() // 初始化
{
mem(P , 0) ;
mem(L , -1) ;
int i ;
for(i = 1 ; i <= n ; i ++)
vert[i].clear() ;
}
void init()
{
clr() ;
int i , j ;
for(i = 1 ; i <= n ; i ++)
{
scanf("%d%d" , &P[i] , &L[i]) ;
int t ;
scanf("%d" , &t) ;
for(j = 1 ; j <= t ; j ++) // 建图
{
int b ;
scanf("%d" , &b) ;
Node tmp ;
tmp.adj = b ;
scanf("%d" , &tmp.c) ;
vert[i].push_back(tmp) ;
}
}
}
bool inq[MAXN] ;
queue q ;
void spfa(int M)
{
while (!q.empty())
q.pop() ;
q.push(1) ;
d[1] = 0 ;
inq[1] = true ;
int u ;
while (!q.empty())
{
u = q.front() ;
q.pop() ;
inq[u] = false ;
int i ;
for(i = 0 ; i < vert[u].size() ; i ++)
{
int v = vert[u][i].adj ;
int ci = vert[u][i].c ;
if(L[v] >= M && L[v] <= M + m)
{
if(d[u] != INF && d[u] + ci < d[v])
{
d[v] = d[u] + ci ;
if(!inq[v])
{
q.push(v) ;
inq[v] = true ;
}
}
}
}
}
}
void solve()
{
int X = max(L[1]- m , 0) ;
int MIN = P[1] ;
int M ;
for(M = X ; M <= L[1] ; M ++) // 枚举等级
{
int i ;
for(i = 1; i <= n ; i ++)
{
d[i] = INF ;
}
mem(inq , 0) ;
spfa(M) ;
for(i = 2 ; i <= n ; i ++)
{
if(L[i] >= M && L[i] <= M + m && d[i] != INF && MIN > d[i] + P[i]) // 注意此处的判断条件
MIN = d[i] + P[i] ;
}
}
printf("%d\n" , MIN) ;
}
int main()
{
while (scanf("%d%d" , &m , &n) != EOF)
{
init() ;
solve() ;
}
return 0 ;
}
|