POJ1062昂贵的聘礼（dijkstra）

题目大意是说有N个物品，每个物品都有自己的价格，但同时某些物品也可以由其他的（可能不止一个）替代品，这些替代品的价格比较“优惠”，问怎么样选取可以让你的花费最少来购买到物品1

由于有N个物品，我们就可以把它们看作是N个点，从其他点到他的优惠关系视做边，又因为最后总是要找到物品1，所以可以看作是从起点0，到将物品1作为终点的最小路劲。然后由于题目是说，这条路劲上不能有两个的等级差超过M，所以我们可以枚举最小等级，将每个点视作最小等级，这样的话就不会掉解。

又由于我们是枚举的最小等级，所以源点0到其他每个点的边的权值就要赋值为那个点的价格，降等级比最小等级要大，或者差距大于M的其他点标记为不合法（也就是不可以走），然后在从合法的路劲中找出最小花费。

 #include<iostream>

 #include<stdio.h>

 #include<string.h>

 #include<map>

 #include<vector>

 #include<set>

 #include<stack>

 #include<queue>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define MAX(a,b) (a > b ? a : b)

 #define MIN(a,b) (a < b ? a : b)

 #define mem(a) memset(a,0,sizeof(a))

 #define MAXN 105

 #define INF 1000000007

 int Price[MAXN],Edge[MAXN][MAXN],Level[MAXN];

 int vis[MAXN], d[MAXN];

 int N,M,ans;

 void init()

 {

     mem(Price); mem(Level);

     for(int i=;i<=N;i++)

     {

         for(int j=;j<=N;j++)

         {

             Edge[i][j] = INF;//初始化每条边都是不连通的

         }

     }

 }

 void read()

 {

     int i,j,X,T,TP;

     for(i=;i<=N;i++)

     {

         scanf("%d%d%d",&Price[i], &Level[i], &X);

         for(j=;j<X;j++)

         {

             scanf("%d %d", &T, &TP);

             Edge[T][i] = TP;//记录边

         }

         Edge[][i] = Price[i];

     }

 }

 int dijkstra()

 {

     for(int i=;i<=N;i++)d[i] = Price[i];//源点0到每个点的权值赋为这个点的价格

     for(int i=;i<=N;i++)

     {

         int temp = INF,x;

         for(int j=;j<=N;j++)if(!vis[j] && d[j]<=temp)temp = d[x = j];

         vis[x] = ;

         for(int j=;j<=N;j++)if(d[x]+Edge[x][j] < d[j] && !vis[j])d[j] = d[x]+Edge[x][j];//要从合法的物品中选取，加上!vis[j]

     }

     return d[];//这里找到的最小值是未知起点的最小值

 }

 int main()

 {

     while(~scanf("%d %d", &M, &N))

     {

         init();

         read();

         ans = INF;

         for(int i=;i<=N;i++)

         {

             int minLevel = Level[i];//将目前的点视作等级最高的点

             for(int j=;j<=N;j++)

             {

                 if(Level[j] - minLevel > M || minLevel > Level[j])vis[j] = ;//如果有比它还低的点，或者差超过M，视为不合法

                 else vis[j] = ;

             }

             int now = dijkstra();

             ans = MIN(ans,  now);

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

POJ1062昂贵的聘礼（dijkstra）

最新文章

热门文章