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 ;  
}