1062 昂贵的聘礼（spfa + 等级枚举） - from lanshui_Yang

解题思路：先建好图，注意是有向图，然后以 1 点为源点，枚举等级的限制，即每次都用spfa 求得1点到其他能够到达的点（由于等级的限制，在一次spfa中可能并不是所有的点都能够到达），最后求出所需最小费用。

Ps：此题中点1的等级可能不是最高的。

请看代码：

 
#include<iostream>  
#include<string>  
#include<algorithm>  
#include<cstring>  
#include<queue>  
#include<cmath>  
#include<vector>  
#include<cstdio>  
#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<Node> 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<int> 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 ;  
}

补充：软件开发 , C++ ,

1062 昂贵的聘礼 （spfa + 等级枚举） - from lanshui_Yang

1062 昂贵的聘礼（spfa + 等级枚举） - from lanshui_Yang