【Dijkstra】POJ1062-昂贵的聘礼

由于物品编号从1开始，我们假定0也是一个物品作为起点，它到其它物品的距离就是各个物品的原始价值。开始时，如果两种物品主人的等级限制M在规定范围以内，且j能用i替换，则将优惠价格视作从i到j的一条权值为优惠价的路径；如果在范围以外，就设为INF。

由于题目中说：“但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。”所以单纯用一次单源最短路径是不可以的。我们依次枚举每一个物品，将它的等级L作为交易中等级最高的那一个，即可以参与交易的等级范围为[L-M,L]，预处理时将这个范围以外的物品强制设置为已经访问过，再进行Dijkstra即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 using namespace std;
 6 const int MAXN=100+5;
 7 const int INF=0x7fffffff;
 8 struct Rec
 9 {
10     int p,l,x;
11     /*依次表示该物品的价格、主人的地位等级和替代品总数*/ 
12     int ins[MAXN];//替代品的编号 
13     int sal[MAXN];//替代品的优惠价 
14 };
15 Rec ob[MAXN];
16 int m,n; 
17 int map[MAXN][MAXN];
18 int vis[MAXN];
19 int ans;
20 
21 int dijkstra()
22 {
23     int trade[MAXN];
24     for (int i=1;i<=n;i++) trade[i]=ob[i].p;
25     for (int i=1;i<=n;i++)
26     {
27         int minnum=INF,minn;
28         for (int j=1;j<=n;j++)
29         {
30             if (vis[j]==0 && trade[j]<minnum)
31             {
32                 minnum=trade[j];
33                 minn=j;
34             }
35         }
36         vis[minn]=1;
37         if (minn==1) break;
38         for (int j=1;j<=n;j++)
39             if (!vis[j] && trade[j]>trade[minn]+map[minn][j]) trade[j]=trade[minn]+map[minn][j];
40     }
41     return trade[1];
42 }
43 
44 int main()
45 {
46     scanf("%d%d",&m,&n);
47     memset(map,0x7F,sizeof(map));
48     for (int i=1;i<=n;i++)
49     {
50         scanf("%d%d%d",&ob[i].p,&ob[i].l,&ob[i].x);
51         map[0][i]=ob[i].p;
52         for (int j=0;j<ob[i].x;j++)
53             scanf("%d%d",&ob[i].ins[j],&ob[i].sal[j]);
54     } 
55     for (int i=1;i<=n;i++)
56         for (int j=0;j<ob[i].x;j++)
57         {
58             if (abs(ob[i].l-ob[ob[i].ins[j]].l)<=m)
59                 map[ob[i].ins[j]][i]=ob[i].sal[j];
60         }
61     
62     
63     ans=INF;
64     for (int i=1;i<=n;i++)
65     {
66         memset(vis,0,sizeof(vis));
67         vis[0]=1;
68         int maxl=ob[i].l;
69         for (int j=1;j<=n;j++)
70             if (i!=j)
71                 if (ob[j].l>maxl || ob[j].l<maxl-m) vis[j]=1; 
72         
73         int nowans=dijkstra();
74         if (nowans<ans) ans=nowans;
75     }
76 
77 
78     cout<<ans<<endl;
79     return 0;
80 }