[poj 1062] 昂贵的聘礼

一开始理解错误了，以为只要是相邻节点的等级差不大于等级限制就ok，原来是必须这个方案中的节点等级差都必须不大于等级限制。

解题思路：因为必须包含1号节点（酋长），所以把所有关于1号节点范围内的等级都列举出来，每次都是不同的图，取最小的就ok了

用的邻接表 + spfa，上代码

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #include <queue>
  5 #define N   102
  6 #define INF 200000000
  7 
  8 int m, n;
  9 
 10 int p[N];
 11 int level[N];
 12 int cm[N];
 13 bool alreadyInQueue[N];
 14 
 15 int max_level;
 16 
 17 int head[N];
 18 int next[N*N];
 19 int edge[N*N];
 20 int cost[N*N];
 21 
 22 void addEdge(int x, int y, int c){
 23     
 24     static int i = 0;
 25     
 26     edge[i] = y;
 27     cost[i] = c;
 28     next[i] = head[x];
 29     head[x] = i;
 30     
 31     i++;
 32 }
 33 
 34 void spfa(){
 35 
 36     for (int i = 1; i <= n; i++){
 37         cm[i] = INF;
 38         alreadyInQueue[i] = false;
 39     }
 40     
 41     cm[1] = 0;
 42     alreadyInQueue[1] = true;
 43     
 44     std::queue<int> q;
 45     q.push(1);
 46     
 47     while(!q.empty()){
 48         int x = q.front();
 49         q.pop();
 50         alreadyInQueue[x] = false;
 51         
 52         for (int e = head[x]; e != -1; e = next[e]){
 53             int y = edge[e];
 54             
 55             if ( level[y] <= max_level
 56                && max_level - level[y] <= m 
 57                && cm[x] + cost[e] < cm[y]){
 58                 cm[y] = cm[x] + cost[e];
 59                 
 60                 if (!alreadyInQueue[y]){
 61                     q.push(y);
 62                     alreadyInQueue[y] = true;
 63                 }
 64             }
 65         }    
 66     }
 67 }
 68 
 69 
 70 int main() {
 71 
 72     scanf("%d%d", &m, &n);
 73     memset(head, -1, sizeof(head));
 74     memset(next, -1, sizeof(next));
 75     
 76     for (int i = 1; i <= n; i++){
 77         int P, L, X;
 78         scanf("%d%d%d", &P, &L, &X);
 79         
 80         p[i] = P;
 81         level[i] = L;
 82 
 83         for (int j = 0; j < X; j++){
 84             int T, V;
 85             scanf("%d%d", &T, &V);
 86             addEdge(i, T, V);    
 87         }
 88     }
 89     
 90     int minimal = p[1];
 91     for (int i = level[1] + m; i >= level[1]; i--){
 92         max_level = i;
 93         
 94         spfa();
 95         
 96         for (int i = 2; i <= n; i++){
 97             if (cm[i] + p[i] < minimal){
 98                 minimal = cm[i] + p[i];
 99             }
100         }
101     }
102 
103     printf("%d", minimal);
104     
105     return 0;
106 }

View Code