poj1062 昂贵的礼物（dijkstra+枚举）

题目大意：买东西，每个东西有了替代品，拥有替代品后可以有优惠价格，每个物品的主人有自己的等级，等级超过m的不能直接或者间接交易，问买1号物品的最低价格是多少。

思路：一开始想到dfs，但等级不超过m的比较麻烦，看了别人的做法后发现把这题转化为最短路实在是太巧妙了（我太弱了），一开始的起点是0，表示什么都没有，每个物品的价格就是从0到i的权值，然后优惠价格就是u和i的权值，就这样转化为了最短路，只不过起点是0，终点是1.而等级问题的话，就依次枚举各个节点的等级，假设为最低等级，然后遍历一下，跑一跑迪杰特斯拉，算出最小值。（用这个方法枚举，dfs应该也行）。

具体看代码的注释吧。

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<string>

#include<math.h>

#include<cmath>

#include<time.h>

#include<map>

#include<set>

#include<vector>

#include<queue>

#include<algorithm>

#include<numeric>

using namespace std;

int m,n;

const int maxn=110;

int dis[maxn],v[maxn],g[maxn][maxn],vis[maxn],vv[maxn];

int djks(){

	for(int i=1;i<=n;i++){

		dis[i]=g[0][i];//表示从0点出发（啥都没有的时候）

	}

	dis[0]=0;

	vis[0]=1;

	for(int i=1;i<=n;i++){

		int p,minn=0x3f3f3f3f;

		for(int j=1;j<=n;j++){

			if(!vis[j]&&dis[j]<minn){

				minn=dis[j];

				p=j;

			}

		}

		vis[p]=1;

		for(int j=1;j<=n;j++){

			if(!vis[j]&&dis[j]>dis[p]+g[p][j]){

				dis[j]=dis[p]+g[p][j];

			}

		}

	}

	return dis[1];//（回到1点）

}

int main(){

	scanf("%d%d",&m,&n);

	memset(g,0x3f3f3f3f,sizeof(g));//图

	for(int i=1;i<=n;i++){

		int k;

		scanf("%d%d%d",&g[0][i],&v[i],&k);//u物品到i物品的花费（到达u节点  去i节点的权值）

		while(k--){

			int u,w;

			scanf("%d%d",&u,&w);

			g[u][i]=w;

		}

	}

	int minn=0x3f3f3f3f;//答案最小值

	for(int i=1;i<=n;i++){//枚举每个节点的等级  将当前节点设为最低等级

		int va=v[i];

		if(vv[va])continue;

		vv[va]=1;

		memset(vis,0,sizeof(vis));

		for(int j=1;j<=n;j++){

			if(v[j]-va>m)vis[j]=1;//排除掉比自己高m以上的

			if(v[j]<va)vis[j]=1;//排除掉比自己低的（因为枚举的是最低等级）

		}

		minn=min(minn,djks());

	}

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

}

巴特西

poj1062 昂贵的礼物（dijkstra+枚举）

最新文章

热门文章