首页 > 代码库 > poj1062（昂贵的聘礼）

poj1062（昂贵的聘礼）

2024-07-07 18:48:08   226人阅读

题目大意：

    中文题目不用翻译。

    说下通俗的题意：M代表等级的权限限制，N代表有N个地方，其中酋长地方的编号永远是第一个编号，所以输入的第一组数据就是酋长的允诺编号为1. 接着有X行能与此地方交换物品和拥有替代品之后的价格。其中P代表这个地方的价值，L代表这个地方的等级。问你怎么用自己的聪明才智使得到达编号1 这个地方的花费最少。

 

测试实例的走法： 4->2->1  一共花费5250.

 

解题思路：

    建图，dijstra最短路。

   注意：

 

代码：

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <sstream>
  4 #include <cstdlib>
  5 #include <cstring>
  6 #include <cstdio>
  7 #include <string>
  8 #include <bitset>
  9 #include <vector>
 10 #include <queue>
 11 #include <stack>
 12 #include <cmath>
 13 #include <list>
 14 //#include <map>
 15 #include <set>
 16 using namespace std;
 17 /***************************************/
 18 #define ll long long
 19 #define int64 __int64
 20 /***************************************/
 21 const int INF = 0x7f7f7f7f;
 22 const double eps = 1e-8;
 23 const double PIE=acos(-1.0);
 24 const int d1x[]= {0,-1,0,1};
 25 const int d1y[]= {-1,0,1,0};
 26 const int d2x[]= {0,-1,0,1};
 27 const int d2y[]= {1,0,-1,0};
 28 const int fx[]= {-1,-1,-1,0,0,1,1,1};
 29 const int fy[]= {-1,0,1,-1,1,-1,0,1};
 30 /***************************************/
 31 void openfile()
 32 {
 33     freopen("data.in","rb",stdin);
 34     freopen("data.out","wb",stdout);
 35 }
 36 /**********************华丽丽的分割线,以上为模板部分*****************/
 37 int lowcost[100],level[100];   //到此地方的最少花费、此地方的等级
 38 int vis[100];   
 39 int map[100][100];
 40 int min1;
 41 void dijstra(int m,int n)
 42 {
 43     int i,j,k;
 44     int min;
 45     min1=INF;
 46     for(int lev=level[1]-m; lev<=level[1]; lev++) //枚举等级区间
 47     {
 48         for(i=1; i<=n; i++)
 49         {
 50             lowcost[i]=map[0][i];
 51             vis[i]=0;
 52         }
 53         int sum=0;
 54         for (j=1; j<=n; j++)
 55             if (level[j]<lev||level[j]>lev+m)   //把不再此等级范围内的地方标记
 56             {
 57                 vis[j]=1;
 58                 sum++;
 59             }
 60         for(i=1; i<=n-1-sum; i++)
 61         {
 62             j=0;
 63             min=INF;
 64             for(k=1; k<=n; k++)
 65             {
 66                 if (!vis[k]&&lowcost[k]<min)
 67                 {
 68                     min=lowcost[k];
 69                     j=k;
 70                 }
 71             }
 72             vis[j]=1;
 73             for(k=1; k<=n; k++)
 74                 if (!vis[k]&&(map[j][k]+lowcost[j]<lowcost[k]))
 75                     lowcost[k]=map[j][k]+lowcost[j];
 76         }
 77         if (lowcost[1]<min1)
 78             min1=lowcost[1];
 79     }
 80 }
 81 int main()
 82 {
 83     int m,n;
 84     while(scanf("%d%d",&m,&n)!=EOF)
 85     {
 86         int i,j;
 87         for(i=0; i<=n; i++)
 88             for(j=0; j<=n; j++)
 89                 map[i][j]=INF;
 90         for(i=1; i<=n; i++)
 91         {
 92             int a,b,c;
 93             scanf("%d%d%d",&a,&b,&c);
 94             level[i]=b;
 95             map[0][i]=a;
 96             for(j=0; j<c; j++)
 97             {
 98                 int x,val;
 99                 scanf("%d%d",&x,&val);
100                 if (map[i][x]>val)  //有向图
101                 {
102                 //    map[i][x]=val;
103                     map[x][i]=val;
104                 }
105             }
106         }
107         dijstra(m,n);
108         printf("%d\n",min1);
109     }
110     return 0;
111 }
View Code

 


联系
我们