poj 1062 昂贵的聘礼

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <algorithm>
  6 using namespace std;
  7 const int INF=0x3f3f3f3f;
  8 const int maxn=110;
  9 struct node
 10 {
 11     int p,l,x; //物品的价格、主人的地位、替代品总数
 12     int num[maxn]; //替代品的编号
 13     int val[maxn]; //优惠价格
 14 } path[maxn];
 15 int m,n; //等级差距,物品总数
 16 int g[maxn][maxn]; //物品i在有第t号替代品情况下的优惠价g[t][i],当t=0时说明i无替代品，此时为原价
 17 int dis[maxn];//源点到各点的权重
 18 bool vis[maxn];
 19 int dijkstra(int x)
 20 {
 21     memset(dis,INF,sizeof(dis));
 22     memset(vis,false,sizeof(vis));
 23     int i,j,k;
 24     int temp=path[x].l;
 25     for(i=0; i<=n; i++)
 26     {
 27         if(path[i].l-temp<=m && path[i].l>=temp)
 28             dis[i]=g[0][i];
 29     }
 30     vis[0]=true;
 31     for(i=0; i<n; i++)
 32     {
 33         int Min=INF;
 34         k=-1;
 35         for(j=0; j<=n; j++)
 36         {
 37             if(!vis[j]&&dis[j]<Min) //在未访问的节点中选择一条最短路
 38             {
 39                 Min=dis[j];
 40                 k=j;
 41             }
 42         }
 43         if(k==-1) //值若没有改变，表示已经找到最短路
 44            break;
 45         vis[k]=true;
 46         for(j=0; j<=n; j++)
 47         {
 48             if(path[j].l-temp<=m && path[j].l>=temp) //保证两人地位差距不超过m
 49             {
 50                 if(!vis[j]&&dis[j]>dis[k]+g[k][j]) //进行松弛操作
 51                     dis[j]=dis[k]+g[k][j];
 52             }
 53         }
 54     }
 55     return dis[1];
 56 }
 57 int main()
 58 {
 59     while(cin>>m>>n)
 60     {
 61         memset(path,0,sizeof(path));
 62         memset(g,INF,sizeof(g));
 63         for(int i=1; i<=n; i++)
 64         {
 65             cin>>path[i].p>>path[i].l>>path[i].x;
 66             for(int j=0; j<path[i].x; j++)
 67                 cin>>path[i].num[j]>>path[i].val[j];
 68             g[0][i]=path[i].p;
 69         }
 70         for(int i=1; i<=n; i++)
 71         {
 72             for(int j=0; j<path[i].x; j++)
 73             {
 74                 if(abs(path[path[i].num[j]].l-path[i].l)<=m) //保证等级差距
 75                 {
 76                     if(g[path[i].num[j]][i]>path[i].val[j]) //更新价格
 77                         g[path[i].num[j]][i]=path[i].val[j];
 78                 }
 79             }
 80         }
 81         int Min=INF;
 82         for(int i=1; i<=n; i++) //求最少金额
 83         {
 84             int ans=dijkstra(i);
 85             if(ans<Min)
 86                 Min=ans;
 87         }
 88         cout<<Min<<endl;
 89     }
 90     return 0;
 91 }
 92 
 93 
 94 /*#include <iostream>
 95 #include <cstdio>
 96 #include <cmath>
 97 #include <cstring>
 98 using namespace std;
 99 
100 #define inf (0x3f3f3f3f)
101 const int maxn = 105;
102 
103 int m, n;
104 struct Goods
105 {
106     int p, l, v;
107     int num[maxn];
108     int val[maxn];
109 }goods[maxn];
110 int map[maxn][maxn];
111 
112 int dijk(int x)
113 {
114     int i, j;
115     int level = goods[x].l;
116     int cost[maxn];
117     bool vis[maxn];
118     memset(cost, inf, sizeof(cost));
119     memset(vis, false, sizeof(vis));
120     for (i=0; i<=n; i++)
121     {
122         if (goods[i].l - level <= m && goods[i].l >= level)
123             cost[i] = map[0][i];
124     }
125     vis[0] = true;
126     for (i=0; i<n; i++)
127     {
128         int min = inf, imin;
129         for (j=0; j<=n; j++)
130         {
131             if (!vis[j] && cost[j] < min)
132             {
133                 imin = j;
134                 min = cost[j];
135             }
136         }
137         if (min == inf)
138             break;
139         vis[imin] = true;
140 
141         for (j=0; j<=n; j++)
142         {
143             if (goods[j].l - level <= m && goods[j].l >= level)
144                 if (cost[j] > cost[imin] + map[imin][j])
145                     cost[j] = cost[imin] + map[imin][j];
146         }
147     }
148     return cost[1];
149 }
150 
151 int main()
152 {
153     while (scanf("%d %d", &m, &n) != EOF)
154     {
155         memset(goods, 0, sizeof(goods));
156         memset(map, inf, sizeof(map));
157         int i, j;
158         for (i=1; i<=n; i++)
159         {
160             scanf("%d %d %d", &goods[i].p, &goods[i].l, &goods[i].v);
161             for (j=0; j<goods[i].v; j++)
162             {
163                 scanf("%d %d", &goods[i].num[j], &goods[i].val[j]);
164             }
165             map[0][i] = goods[i].p;
166         }
167         for (i=1; i<=n; i++)
168         {
169             for (j=0; j<goods[i].v; j++)
170             {
171                 if (abs(goods[goods[i].num[j]].l - goods[i].l) <= m)
172                 {
173                     if (map[goods[i].num[j]][i] > goods[i].val[j])
174                     {
175                         map[goods[i].num[j]][i] = goods[i].val[j];
176                     }
177                 }
178             }
179         }
180         int min = inf;
181         for (i=1; i<=n; i++)
182         {
183             int tmp = dijk(i);
184             if (tmp < min)
185                 min = tmp;
186         }
187         printf("%d\n", min);
188     }
189     return 0;
190 }
191 */