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 ;
}
上一篇:oracle特殊字符的ascii值


下一篇:[Everyday Mathematics]20150303