POJ 1062 昂贵的聘礼

　　SPFA　
　第二次用到超级源点这个概念，依稀记得第一次用还是小时候......
　逆向建图，添加超级源的时候是顺向建立。
　　　　0号点为超级源。
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <algorithm>
  7 #include <queue>
  8 
  9 using namespace std;
 10 
 11 struct N
 12 {
 13     int g,p,v;
 14     N *next;
 15 }*head[110];
 16 
 17 N *creat()
 18 {
 19     N *p = (N*)malloc(sizeof(N));
 20     p->next = NULL;
 21     return p;
 22 }
 23 
 24 void link(int u,int v,int w)
 25 {
 26     N *p = creat();
 27     p->p = w;
 28     p->v = v;
 29     p->next = head[u]->next;
 30     head[u]->next = p;
 31 }
 32 
 33 int dis[110];
 34 
 35 int bellman_ford(int low,int high,int n)
 36 {
 37     queue<int> q;
 38 
 39     N *p;
 40 
 41     int i,t;
 42     for(i = 0;i <= n; ++i)
 43     {
 44         dis[i] = head[1]->p;
 45     }
 46     dis[0] = 0;
 47 
 48     q.push(0);
 49 
 50     while(!q.empty())
 51     {
 52       
 53         t = q.front();
 54         q.pop();
 55         for(p = head[t]->next;p != NULL; p = p->next)
 56         {
 57             if(head[p->v]->g >= low && head[p->v]->g <= high && dis[t] + p->p < dis[p->v])
 58             {
 59                 dis[p->v] = p->p + dis[t];
 60                 q.push(p->v);
 61             }
 62         }
 63     }
 64     return dis[1];
 65 }
 66 
 67 int main()
 68 {
 69     int temp,MIN;
 70 
 71     int gap,n;
 72 
 73     int i,j;
 74 
 75     int p,g,x;
 76 
 77     int id,c;
 78 
 79     while(cin>>gap>>n)
 80     {
 81 
 82         for(i = 0; i <= n; i++)
 83         {
 84             head[i] = creat();
 85         }
 86 
 87         for(i = 1; i <= n; i++)
 88         {
 89             cin>>p>>g>>x;
 90             head[i]->g = g;
 91             head[i]->p = p;
 92             link(0,i,p);
 93 
 94             for(j = 0; j < x; j++)
 95             {
 96                 cin>>id>>c;
 97                 link(id,i,c);
 98             }
 99         }
100 
101         MIN = head[1]->p;
102 
103         for(i = head[1]->g - gap; i <= head[1]->g; i++)
104         {
105         
106             temp = bellman_ford(i,i+gap,n);
107 
108             MIN = MIN < temp ? MIN : temp;
109         }
110 
111         cout<<MIN<<endl;
112     }
113     return 0;
114 }